벽 만들기 게임은 두 사람이 번갈아 두는 보드게임이고, 요즘 유행이다.
게임은 H×W 크기의 판에서 진행한다. 판의 각 칸은 빈 칸, 표시된 칸, 벽 중 하나다. 게임을 시작할 때 판에는 벽이 하나도 없다.
두 사람은 다음과 같이 번갈아 한 번씩 움직인다.
- 빈 칸을 하나 고른다. 빈 칸은 표시된 칸도 아니고 벽도 아닌 칸이다. 고를 칸이 없으면 그 사람이 진다.
- 고른 칸에서 위, 아래, 왼쪽, 오른쪽 네 방향으로 각각 한 칸씩 나아가면서 지나간 칸을 모두 벽으로 바꾸고, 벽에 닿거나 판 밖으로 나가게 되면 그 방향을 멈춘다. 고른 칸도 벽으로 바뀐다.
표시된 칸은 1번에서 고를 수 없지만, 2번에서 벽으로 바뀔 수는 있다.
그림 1은 셋째 행 넷째 열의 칸을 고른 움직임의 예다.

그림 1: 벽 만들기 게임에서 한 번 움직인 예.
두 사람이 모두 최선을 다해 둘 때 주어진 처음 판에서 누가 이기는지 판정하는 프로그램을 작성하시오.