남우는 미로에 갇혔습니다. 미로는 n × m 크기의 격자로 이루어져 있고, 각 격자 칸은 남우, 출구, 유령, 빈 공간, 벽 중 하나로 이루어져 있습니다. 남우가 출구로 이동하면 미로를 탈출하게 되며, 출구로 이동하기 위해 시작 위치에서 상하 좌우로 인접한 칸 중 격자를 벗어나지 않으면서 벽이 아닌 칸을 골라 이동하는 것을 반복하게 됩니다.

만약 n 이 4이고, m 이 6인 격자가 다음과 같이 주어졌다면, 남우는 다음 경로로 탈출이 가능합니다.

이 미로 안에 유령이 있는 경우도 있습니다. 남우는 유령을 무서워 하기 때문에 유령을 마주치지 않고 탈출하고 싶습니다. 남우는 1초에 한 칸씩 상하 좌우로 인접한 칸 중 격자를 벗어나지 않으며 벽이 아닌 곳으로 이동이 가능하지만, 유령은 1초에 한 칸씩 상하 좌우로 인접한 칸 중 격자를 벗어나지 않는 어떤 칸으로든 이동이 가능합니다. 즉, 유령은 벽도 통과하여 이동하는 것이 가능합니다. 유령은 최선을 다해서 남우를 잡으려 하기에, 남우는 똑똑하게 유령을 피해 출구로 이동해야 합니다. 남우가 이동하는 도중 유령과 마주치게 되거나, 정확히 출구에 도착하는 순간 유령과 마주치게 되더라도 남우는 탈출에 실패하게 됩니다. 단, 유령은 필요에 따라 움직이지 않아도 됨에 유의합니다.

위의 그림에서 유령이 다음과 같이 2마리가 놓여있다면, 남우는 여전히 동일한 경로를 통해 5초 만에 성공적으로 탈출이 가능합니다. 남우가 탈출하는 동안 유령이 절대 남우를 잡을 수 없기 때문에 가능한 경우입니다.

하지만 초기 격자 상태가 다음과 같이 주어진 경우라면, 남우는 절대로 유령을 피해 탈출할 수 없습니다.

그 이유는 다음과 같습니다. 우선 남우는 탈출을 위해 처음에 꼭 아래 방향으로 이동해야 합니다.

남우는 출구로 가기 처음 3초 동안 꼭 다음과 같이 이동해야만 하는데, 이때 두 유령 모두 오른쪽으로만 3칸씩 이동한다고 생각해보겠습니다.

그러면 이제 남우는 두 유령에 둘러싸이게 되어 어떻게 이동해도 탈출할 수 없게 됩니다.

초기 격자 상태가 주어졌을 때, 남우가 유령을 피해 출구까지 이동하여 탈출하는 것이 가능한지 판단하는 프로그램을 작성해보세요.

본 문제의 저작권은 (주)브랜치앤바운드에 있으며, 저작자의 동의 없이 무단 전재/복제/배포를 금지합니다.

• [2024-07-24] 테스트케이스가 추가되었습니다.