← 返回题目列表

AtCoder · awc0076_d

D. 逃离迷宫

中文机器翻译题面 查看原题

分数: 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 细胞以四个方向(上、下、左、右)之一移动到相邻的传代细胞,或留在当前细胞上。他无法移动到墙壁牢房或网格之外。留在当前单元格始终是一个可用的选择。
  2. 捕获检查1: 高桥移动后,如果高桥与任何警卫机器人在同一个牢房,高桥就会被抓住并 逃生失败。在这种情况下,本轮的剩余步骤不被执行。
  3. 转义检查: 如果高桥在捕获检查 1 中没有被抓住,并且高桥在出口处 (G_r, G_c),那么 越狱成功。在这种情况下,本轮的剩余步骤不被执行。
  4. 警卫机器人的动作: 如果既没有发生逃生成功,也没有发生逃生失败,则所有警卫机器人同时移动 1 步骤(移动规则如下所述)。每个机器人独立于其他机器人确定其目的地。允许多个机器人占据同一个单元。
  5. 捕获检查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