分数: 400 分
问题陈述
高桥被困在一个 N \times M 网格状迷宫。网格的每个单元格要么是一个通道(.)或墙(#)。一个单元格表示为 (r, c) (行 r,列 c),其中行和列都从 1。行号从上到下增加,列号从左到右增加。也就是说,从细胞 (r, c),“向上”指的是单元格 (r-1, c),“向下”指的是单元格 (r+1, c),“左”指单元格 (r, c-1),“右”指单元格 (r, c+1).
高桥目前在牢房 (S_r, S_c) 并试图通过到达牢房的出口逃跑 (G_r, G_c).
有 K 在迷宫中巡逻的警卫机器人,以及 i第个警卫机器人的初始位置是单元格 (P_i, Q_i)。不同的警卫机器人最初可能被放置在同一个牢房中。
每个警卫机器人的动作是 仅根据高桥的立场确定性地确定,根据下面描述的移动规则。高桥知道整个迷宫的结构,以及看守机器人的所有移动规则。
高桥和警卫机器人重复如下回合。第一个回合是回合 1,依次轮流 2, 3, \ldots。游戏开始时(回合第 1 步之前)不执行捕获检查 1)。每回合按以下顺序进行:
- 高桥的动作: 高桥选择移动 1 细胞以四个方向(上、下、左、右)之一移动到相邻的传代细胞,或留在当前细胞上。他无法移动到墙壁牢房或网格之外。留在当前单元格始终是一个可用的选择。
- 捕获检查1: 高桥移动后,如果高桥与任何警卫机器人在同一个牢房,高桥就会被抓住并 逃生失败。在这种情况下,本轮的剩余步骤不被执行。
- 转义检查: 如果高桥在捕获检查 1 中没有被抓住,并且高桥在出口处 (G_r, G_c),那么 越狱成功。在这种情况下,本轮的剩余步骤不被执行。
- 警卫机器人的动作: 如果既没有发生逃生成功,也没有发生逃生失败,则所有警卫机器人同时移动 1 步骤(移动规则如下所述)。每个机器人独立于其他机器人确定其目的地。允许多个机器人占据同一个单元。
- 捕获检查2: 警卫机器人移动后,如果高桥与任何警卫机器人在同一牢房,高桥就会被抓住并 逃生失败.
这些回合会重复,直到发生逃脱成功或逃脱失败。
警卫机器人移动规则
每个警卫机器人要么移动 1 细胞沿四个方向(上、下、左、右)之一移动到相邻的传代细胞,或停留在其当前细胞上。它不能移动到壁单元或网格之外。
每个警卫机器人的目的地确定如下。首先,列举运动候选人。候选者是:在目的地在网格内并且是一段通道的情况下向上、向下、向左或向右移动,以及停留在当前单元格上(最多 5 候选人)。
对于每个候选者,计算 从机器人移动后的位置到高桥在该回合移动后的位置的曼哈顿距离(他在步骤 1 后的位置)。这里,细胞之间的曼哈顿距离 (r_1, c_1) 和 (r_2, c_2) is |r_1 - r_2| + |c_1 - c_2|,无论中间是否有墙壁。
在候选者中,选择最小化曼哈顿距离的那个。如果存在多个具有最小曼哈顿距离的候选者,则根据优先级顺序选择优先级最高的候选者: 上、下、左、右、停留 (从最高优先级到最低优先级列出)。
输出什么
判断高桥在最佳行动时能否成功逃脱。这里,“最优行动”是指,如果存在导致逃脱成功的行动序列,则他选择这样的序列,并且在这些序列中,他采取行动以最小化逃脱成功的回合数。
如果可以逃脱,则输出逃脱成功的最小回合数。
如果高桥无论如何行动都无法逃脱(例如,他在到达出口之前不可避免地被抓住,或者他可以避免被抓住但永远无法到达出口),则输出 -1.
约束
- 1 \leq N \leq 8
- 1 \leq M \leq 8
- 0 \leq K \leq 2
- 1 \leq S_r \leq N
- 1 \leq S_c \leq M
- 1 \leq G_r \leq N
- 1 \leq G_c \leq M
- 1 \leq P_i \leq N (1 \leq i \leq K)
- 1 \leq Q_i \leq M (1 \leq i \leq K)
- (S_r, S_c) \neq (G_r, G_c)
- 高桥的初始位置、出口、各个警卫机器人的初始位置都是通道(
.). - 高桥的初始位置与每个警卫机器人的初始位置不同。
- 所有输入值均为整数(网格字符串除外)。
输入
N M K S_r S_c G_r G_c P_1 Q_1 P_2 Q_2 \vdots P_K Q_K C_1 C_2 \vdots C_N
- 第一行包含行数 N,列数 M,以及警卫机器人的数量 K,用空格分隔。
- 第二行包含 Takahashi 的初始行 S_r 和专栏 S_c,用空格分隔。
- 第三行包含出口行 G_r 和专栏 G_c,用空格分隔。
- 以下 K 行给出了警卫机器人的初始位置。如果 K = 0,这部分包括 0 行且不存在。
- 对于 i-th (1 \leq i \leq K) 警卫机器人,其第一排 给出 P_i 和专栏 Q_i ,用空格分隔。
- 以下 N 行包含字符串 C_i 长度 M 代表网格的每一行。每个字符要么是
.(段落)或#(墙)。 - C_i 代表的信息 i第行 (1 \leq i \leq N) 从顶部。的 j- 第一个字符 C_i 对应cell的状态 (i, j).
输出
如果高桥在最佳行动时能够成功逃脱,则在一行中输出逃脱成功的最小回合数。如果他不能成功,则输出 -1.
示例输入 1
3 3 0 1 1 1 3 ... ... ...
示例输出 1
2
示例输入 2
3 1 1 1 1 3 1 2 1 . . .
示例输出 2
-1
示例输入 3
5 5 1 1 1 5 5 3 3 ..... .###. .#... .#.#. .....
示例输出 3
16
示例输入 4
8 8 2 1 1 8 8 1 8 8 1 ........ .######. .#....#. .#.##.#. .#.##.#. .#....#. .######. ........
示例输出 4
-1
示例输入 5
1 2 0 1 1 1 2 ..
示例输出 5
1