Mapping the Route

Finding a path through a maze is a classic computing problem. Here a maze is a rectangular grid of square cells, and each cell may have walls on its north, south, east, and/or west sides. One cell is the start and another is the goal. Your task is to find the unique route from the start to the goal using exactly the algorithm below, label every cell on that route with its position in the route, mark the cells that were visited but are not on the route, and draw the maze.

The robot begins in the start cell. From its current cell it tries to move in this fixed order: west, then north, then east, then south. It may move in the chosen direction when (a) no wall blocks that side and (b) it has not already been in the neighbouring cell in that direction. When it reaches the goal, the trip ends. When it reaches a cell from which no move is possible, it backtracks to the previous cell and tries the next untried direction there.

Consider the small maze on the left below: two cells tall and three cells wide, with the start marked S and the goal marked G. The robot first tries west (blocked by a wall), then north (blocked), then east (blocked), and finally south (which succeeds). From the new cell it eventually moves east; there it could move west, but that cell is already visited, so it moves north and succeeds, only to hit a dead end and backtrack; it then moves east and finally north into the goal. The picture on the right shows what is drawn: the start cell is labeled 1, every cell on the route to the goal (including the goal) is labeled with its sequence number, and every cell that was visited but is not on the route is labeled with question marks.

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

Number the rows from 1 at the north and the columns from 1 at the west; in the maze above the start is row 1, column 1 and the goal is row 1, column 3.

The input contains one or more mazes. Each maze begins with six integers: the height (number of rows) and the width (number of columns), then the row and column of the start cell, then the row and column of the goal cell. No maze has more than 12 rows or 12 columns, and a route from the start to the goal always exists.

After those six integers come one integer per cell, in row-major order. Each value encodes that cell's walls: add 1 if it has a wall on its east side and add 2 if it has a wall on its south side. So 0 means no east or south wall, 2 means a south wall only, and 3 means both an east and a south wall. The outer border of the maze always has the walls needed to keep the robot inside, and those border walls are not listed in the input.

The input ends with a line of six zeros, which is not a maze.

For each maze, draw it exactly as in the example, labeled and prefixed by its maze number; mazes are numbered starting from 1.

Each maze is printed as the header line Maze N, then one blank line, then the drawing. Every cell occupies three characters: a route cell shows its sequence number right-justified, a visited cell that is not on the route shows ???, and a never-visited cell shows three spaces. Adjacent cells are separated by | where a wall stands between them and by a single space otherwise; horizontal walls are drawn with ---, open horizontal sides with three spaces, and + marks every corner. Print two blank lines between one maze and the next.