题目描述

在计算机领域中，寻找穿过迷宫的路径是一个常见的问题。在本题中，迷宫由一个矩形的正方形单元格数组组成，每个单元格的北、南、东和（或）西方向可能有墙。其中一个单元格将被指定为起点，另一个单元格将被指定为目标点。你的任务是找到从起点到目标点的唯一路径，给路径上的每个单元格标记上它在路径中的顺序编号，标识出已访问但不在路径上的单元格，并展示迷宫。

你用来寻找穿过迷宫路径的算法必须是下面描述的那种。设想有一个机器人位于起点单元格。机器人首先尝试从该单元格向西移动，然后向北，接着向东，最后向南，按此顺序进行。如果满足以下两个条件，机器人就可以朝选定的方向移动：$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$。迷宫周边的单元格总是有合适的墙来防止机器人离开迷宫；这些墙在输入数据中不会被指定。

输入数据中的最后一个迷宫后面会跟着六个零。

输出

对于每个迷宫，按照上面的示例和下面预期的输出格式展示迷宫，加上适当的标签，并在前面加上迷宫的编号。迷宫按顺序编号，从$1$开始。

输入示例

2 3 1 1 1 3
1 1 0
0 0 0

4 3 3 2 4 3
0 3 0
0 2 0
0 3 0
0 1 0

0 0 0 0 0 0

输出示例

迷宫 1

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


迷宫 2

+---+---+---+
|??? ???|???|
+   +---+   +
|  3   4   5|
+   +---+   +
|  2   1|  6|
+   +---+   +
|       |  7|
+---+---+---+

来源

1997年北美中北部地区竞赛