칠하기 timer 2s memory 1024MB

N*M 크기의 격자가 주어진다. 일부 칸은 막혀서 움직일 수 없는 칸이고, 나머지 칸들은 서로 자유자래로 움직일 수 있는 칸이다. 여기에 페인트를 칠하려고 한다.

페인트를 칠하는 규칙은 다음과 같다.

1) 움직일 수 있는 칸 아무거나 하나를 시작점으로 잡을 수 있다.

2) 이제 가로방향 또는 세로방향으로 움직일 수 있는데, 가로방향으로 움직일 때는 파란색 페인트로, 세로방향으로 움직일 때는 노란색 페인트를 이용한다.

3) 바닥이 굉장히 미끄럽기 때문에 중간에 멈출수가 없다. 즉, 한쪽 방향으로 계속 움직여 격자에 끝에 도달하거나 움직일 수 없는 칸에 도착했을 때만 움직임을 멈추고 방향을 바꿀 수 있다.

위 과정을 무한히 반복했을 때, 움직일 수 있는 모든 칸에 노란색 페인트와 파란색 페인트가 모두 적어도 한번씩 칠해질 수 있는지 판별하시오.