미로 경로 그리기

미로에서 길을 찾는 것은 컴퓨터의 고전적인 문제입니다. 이 문제에서 미로는 정사각형 칸들이 직사각형 모양으로 배열된 격자이며, 각 칸은 북쪽, 남쪽, 동쪽, 서쪽 중 일부에 벽을 가질 수 있습니다. 한 칸은 출발점이고 다른 한 칸은 도착점입니다. 여러분이 할 일은 아래에 설명된 알고리즘을 그대로 사용하여 출발점에서 도착점까지의 유일한 경로를 찾고, 그 경로 위의 각 칸에 순서 번호를 붙이고, 방문했지만 경로에는 포함되지 않은 칸을 표시한 뒤, 미로를 그리는 것입니다.

로봇은 출발 칸에서 시작합니다. 현재 칸에서 로봇은 서쪽, 북쪽, 동쪽, 남쪽의 고정된 순서로 이동을 시도합니다. 다음 두 조건이 모두 성립할 때에만 그 방향으로 이동합니다. (a) 그 방향을 막는 벽이 없어야 하고, (b) 그 방향의 이웃 칸을 아직 방문한 적이 없어야 합니다. 도착점에 다다르면 이동을 끝냅니다. 더 이상 이동할 수 없는 칸에 이르면 직전에 있던 칸으로 되돌아가 아직 시도하지 않은 다음 방향을 시도합니다.

아래 왼쪽의 작은 미로를 봅시다. 높이는 두 칸, 너비는 세 칸이며 출발점은 S, 도착점은 G로 표시되어 있습니다. 로봇은 먼저 서쪽을 시도하지만 벽에 막히고, 이어서 북쪽(막힘), 동쪽(막힘)을 시도한 뒤 마지막으로 남쪽으로 이동에 성공합니다. 새 칸에서 로봇은 결국 동쪽으로 이동합니다. 그곳에서 서쪽으로 갈 수도 있지만 그 칸은 이미 방문했으므로 북쪽으로 이동해 성공하지만, 막다른 길을 만나 되돌아옵니다. 그 뒤 동쪽으로 이동하고 마지막으로 북쪽으로 이동하여 도착점에 들어갑니다. 오른쪽 그림은 출력 결과를 보여줍니다. 출발 칸은 1로 표시되고, 도착점까지의 경로에 있는 모든 칸(도착점 포함)은 순서 번호로 표시되며, 방문했지만 경로에 없는 모든 칸은 물음표로 표시됩니다.

+---+---+---+        +---+---+---+
| S |   | G |        |  1|???|  5|
+   +   +   +        +   +   +   +
|           |        |  2   3   4|
+---+---+---+        +---+---+---+

행은 북쪽부터 1, 열은 서쪽부터 1로 번호를 매깁니다. 위 미로에서 출발점은 1행 1열, 도착점은 1행 3열입니다.

입력에는 하나 이상의 미로가 있습니다. 각 미로는 여섯 개의 정수로 시작합니다. 처음 두 수는 미로의 높이(행의 수)와 너비(열의 수)이고, 다음 두 수는 출발 칸의 행과 열, 마지막 두 수는 도착 칸의 행과 열입니다. 어떤 미로도 행이 12개, 열이 12개를 넘지 않으며, 출발점에서 도착점까지 가는 경로는 항상 존재합니다.

여섯 개의 정수 뒤에는 칸마다 하나씩, 행 우선 순서로 정수가 주어집니다. 각 값은 그 칸의 벽을 나타냅니다. 동쪽에 벽이 있으면 1을 더하고, 남쪽에 벽이 있으면 2를 더합니다. 따라서 0은 동쪽·남쪽 벽이 모두 없음을, 2는 남쪽 벽만 있음을, 3은 동쪽과 남쪽 벽이 모두 있음을 뜻합니다. 미로의 바깥 테두리에는 로봇이 밖으로 나가지 못하도록 항상 필요한 벽이 있으며, 이 테두리 벽은 입력에 포함되지 않습니다.

입력은 여섯 개의 0으로 이루어진 줄로 끝나며, 이는 미로가 아닙니다.

각 미로에 대해 예시와 똑같이 미로를 그리고, 미로 번호를 앞에 붙입니다. 미로는 1번부터 차례로 번호를 매깁니다.

각 미로는 머리글 줄 Maze N을 출력한 뒤 빈 줄 하나를 두고 그림을 출력합니다. 모든 칸은 세 글자를 차지합니다. 경로에 있는 칸은 순서 번호를 오른쪽 정렬로 표시하고, 방문했지만 경로에 없는 칸은 ???로, 한 번도 방문하지 않은 칸은 공백 세 개로 표시합니다. 이웃한 두 칸 사이에 벽이 있으면 |로, 없으면 공백 하나로 구분합니다. 가로 벽은 ---로, 벽이 없는 가로 면은 공백 세 개로 그리며, 모든 모서리는 +로 표시합니다. 한 미로와 다음 미로 사이에는 빈 줄을 두 개 출력합니다.