칠하기

$N \times M$ 칸으로 이루어진 격자가 있다. 격자의 일부 칸은 막혀 있어 들어갈 수 없고, 나머지 칸은 갈 수 있다. 다음 규칙에 따라 갈 수 있는 칸에 색을 칠한다.

1. 갈 수 있는 칸 중 하나를 현재 칸으로 정하고 시작한다.
2. 방향(위, 아래, 왼쪽, 오른쪽 중 하나)을 정한다. 격자의 경계에 닿거나 이동하려는 다음 칸이 막혀 있을 때까지 그 방향으로 계속 이동한다. 중간에 멈출 수 없다.
3. 멈출 때까지 가로 방향(왼쪽 또는 오른쪽)으로 이동했다면, 이동한 칸과 시작 칸을 모두 노란색으로 칠한다. 세로 방향(위 또는 아래)으로 이동했다면, 이동한 칸과 시작 칸을 모두 파란색으로 칠한다. 시작 칸의 바로 다음 칸이 막혀 있어 한 칸도 움직이지 못한 경우에도, 그 방향에 해당하는 색으로 시작 칸을 칠한다.
4. 모든 갈 수 있는 칸을 노란색으로 적어도 한 번, 파란색으로 적어도 한 번 칠했다면 성공하고 종료한다.
5. 그렇지 않다면 마지막으로 이동이 멈춘 칸에서 다시 시작하여 2번부터 4번까지 반복한다. 이 과정을 무한히 반복해도 모든 갈 수 있는 칸을 노란색과 파란색으로 각각 적어도 한 번씩 칠할 방법이 없다면 실패이다.

예를 들어 모든 칸이 갈 수 있는 $2 \times 3$ 격자를 보자. 왼쪽 위 $(0, 0)$에서 시작하면 어떻게 이동해도 모든 갈 수 있는 칸을 파란색과 노란색으로 각각 적어도 한 번씩 칠할 수 없다. 반면 $(0, 1)$에서 시작해 오른쪽 그림처럼 이동하면 가능하다.

격자의 크기와 배치가 주어졌을 때, 모든 갈 수 있는 칸을 파란색과 노란색으로 칠할 수 있는지 구한다.

이 문제를 풀기 위해 다음 함수를 구현해야 한다.

• int yellowblue( int N, int M, vector<string> V ) ; 이 함수는 한 번만 호출된다. N과 M은 격자의 크기이다. V는 크기가 N인 string 배열(vector)이고, 각 string의 길이는 M이다. $(i, j)$ 칸이 갈 수 있는 칸이면 V[i]의 $j$번째 글자는 '.'이고, 막혀 있는 칸이면 '#'이다. 어떤 위치에서 시작하여 모든 갈 수 있는 칸을 파란색과 노란색으로 각각 적어도 한 번씩 칠할 수 있다면 1을, 그렇지 않다면 0을 반환해야 한다.

$1 \le N, M \le 1000$. 전체 격자에 갈 수 있는 칸이 적어도 하나 존재한다.