塞格德大学的人工智能研究人员正在举办一场机器人编程竞赛。
你的朋友 Hanga 决定参加比赛。由于著名的匈牙利牧羊犬品种 Puli 非常聪明，所以该比赛的目标定为编程实现顶级的 Pulibot。
Pulibot 将在由 网格组成的迷宫中进行测试。
网格的行从北到南编号为 到 ，网格的列从西到东编号为 到 。
我们将位于网格的第 行和第 列的单元格（, ）称为单元格 。
考虑一个单元格 （，），和它相邻的有 个单元格。
- 单元格 被称为单元格 的西邻；
- 单元格 被称为单元格 的南邻；
- 单元格 被称为单元格 的东邻；
- 单元格 被称为单元格 的北邻。
如果 或 或 或 成立，则单元格 称为迷宫的边界。每个不是迷宫边界的单元格要么是障碍，要么是空的。
此外，每个空单元格都有一个颜色，由 和 之间的非负整数表示，包括 和 。最初，每个空单元格的颜色为 。
例如，考虑一个迷宫，， ， 包含一个障碍单元格 。
唯一的障碍单元格用 表示。迷宫的边界单元格被阴影覆盖。
每个空单元格中的数字表示它的颜色。
从单元格 到单元格 的长度为 （）的路径
是一个空单元格序列 ，序列中的空单元格两两不同。其中对于每个 （），单元格 和 是相邻的。
注意长度为 的路径正好包含 个单元格。
在比赛中，研究人员设置了一个迷宫，其中至少有一条从单元格 到单元格 的路径。注意，这意味着单元格 和 保证为空。
Hanga 不知道迷宫中哪些单元格是空的，哪些单元格是障碍。
你的任务是帮助 Hanga 对 Pulibot 进行编程，使其能够在研究人员设置的未知迷宫中找到从单元格 到单元格 的最短路径（即长度最小的路径）。
Pulibot 的说明和比赛规则如下所述。
注意，在题面的最后一部分描述了一个显示工具，该工具可以用于可视化 Pulibot。
Pulibot 说明
对每个单元格 （ ，），其状态定义为一个整数，具体如下：
- 如果单元格 是边界，则其状态为 ；
- 如果单元格 是障碍，则其状态为 ；
- 如果单元格 是空的，那么它的状态就是单元格的颜色。
Pulibot 的程序是按一系列步骤执行的。在每一步中，Pulibot 都会识别附近单元格的状态，然后执行一条指令。它执行的指令由识别的状态决定。以下是更准确的描述。
假设在当前步骤开始时，Pulibot位于单元格 ，这是一个空单元格。该步骤执行如下：
- 首先，Pulibot 识别当前状态数组，即数组 ， 它包含单元格 及其所有相邻单元格的状态：
- 表示单元格 的状态。
- 表示西邻的状态。
- 表示南邻的状态。
- 表示东邻的状态。
- 表示北邻的状态。
- 然后，Pulibot 确定与所识别的状态数组相对应的指令 。
- 最后，Pulibot 执行这条指令：它将单元格 的颜色设置为 ，然后它执行动作 , 是以下动作之一：
- 停留 在单元格 ；
- 移动 到 个邻居之一；
- 终止程序。
例如，考虑下图左侧显示的场景。Pulibot 当前位于单元格，颜色为。
Pulibot 识别出状态数组 。Pulibot 可能有一个程序，该程序根据所识别的数组，将当前单元格的颜色设置为 ，然后向东移动，如图的中间和右侧所示：
机器人比赛规则
- 在开始时，Pulibot 被放置在单元格 并开始执行其程序。
- 不允许 Pulibot 移动到非空单元格。
- Pulibot 的程序必须在最多 步后终止。
- 在 Pulibot 的程序终止后，迷宫中的空单元格的着色满足以下要求：
- 存在从 到 的最短路径，路径中包括的每个单元格的颜色为 。
- 所有其他空单元格的颜色为 。
- Pulibot 可以在任何空单元格终止其程序。
例如，下图显示了一个可能的迷宫，其中。左侧显示了初始配置，右侧显示了程序终止后空单元格的一种可以接受的着色：
