P13128 [GCJ 2019 Finals] Go To Considered Helpful
题目描述
Marlin 是一条丢失了儿子的鱼，正在努力寻找他的儿子。幸运的是，他遇到了正在和兄弟 Wally 与 Seymour 一起游泳的海龟 Cynthia。Cynthia 知道 Marlin 需要去哪里，并且她可以非常精确地给出指引。虽然 Marlin 很聪明，能够完美地按照指令行动，但要记住一长串指令还是很困难的。Cynthia 需要想办法让指令列表尽可能简短。
Marlin 生活在一个有 $\mathbf{R}$ 行 $\mathbf{C}$ 列的矩阵中。矩阵中的某些格子是危险的，不能进入。Marlin 和他的儿子目前分别位于两个不同的非危险格子中。Marlin 的儿子不会移动。Cynthia 决定以程序的形式给 Marlin 指路，这个程序由若干条指令组成，每条指令占一行。每条指令有以下 5 种类型之一：
- $\mathbf{N}$：向北（上）移动一格，
- $\mathbf{S}$：向南（下）移动一格，
- $\mathbf{W}$：向西（左）移动一格，
- $\mathbf{E}$：向东（右）移动一格，
- $\mathbf{G}(\mathbf{i})$：跳转到指令列表的第 $i$ 行（从 1 开始计数）。
每当执行前 4 种指令中的任意一种后，如果还有下一行指令，Marlin 会跳到下一行继续执行。如果没有下一行指令，Marlin 就会原地停留，永远不再移动。
例如，假如 Marlin 执行如下程序：
1. $\mathbf{N}$
2. $\mathbf{E}$
3. $\mathbf{G}(6)$
4. $\mathbf{S}$
5. $\mathbf{G}(1)$
6. $\mathbf{W}$
7. $\mathbf{G}(4)$
他会先向北移动（第 1 行），然后向东移动（第 2 行），接着跳转到第 6 行（第 3 行），然后向西移动（第 6 行），再跳转到第 4 行（第 7 行），然后向南移动（第 4 行），再跳转到第 1 行（第 5 行），然后向北移动（第 1 行），如此循环往复。
如果某一时刻 Marlin 和他的儿子处于同一个格子，他们就会团聚，Marlin 也会停止执行任何指令。海龟 Cynthia 想知道，能够让 Marlin 安全到达他儿子所在格子的最短程序需要多少行指令，且在此过程中 Marlin 不能进入危险格子，也不能走出矩阵边界。所有 $\mathbf{G}$ 指令必须跳转到程序中已存在的行。
输入格式
输入的第一行为测试用例数 $\mathbf{T}$。接下来有 $\mathbf{T}$ 组测试数据。每组测试数据的第一行为两个整数 $\mathbf{R}$ 和 $\mathbf{C}$，表示矩阵的行数和列数。接下来有 $\mathbf{R}$ 行，每行包含一个长度为 $\mathbf{C}$ 的字符串。第 $i$ 行第 $j$ 列的字符 $\mathbf{A}_{ij}$ 表示矩阵中第 $i$ 行第 $j$ 列的格子。若该格子为危险格子，则为字符 $\#$；若为 Marlin 当前所在格子，则为大写字母 $\mathbf{M}$；若为 Marlin 儿子当前所在格子，则为大写字母 $\mathbf{N}$；若为未被占用的非危险格子，则为 $\mathbf{.}$。
输出格式
对于每组测试数据，输出一行，格式为 `Case #x: y`，其中 $x$ 为测试用例编号（从 1 开始），$y$ 为在上述条件下能让 Marlin 到达他儿子所在格子的最短程序所需的指令行数。如果不存在这样的程序，则输出 $\text{IMPOSSIBLE}$。
说明/提示
**样例说明**
下面是每个样例的最短程序示例。
- 样例 1：
```
1: W
2: N
3: S
4: G(1)
```
或
```
1: W
2: N
3: W
4: G(3)
```
- 样例 2：
```
1: N
2: W
3: W
4: S
5: W
6: W
7: N
```
- 样例 3：
```
1: W
2: W
3: N
4: N
5: G(2)
```
- 样例 4：
```
1: W
2: W
3: N
4: N
5: E
6: G(1)
```
**样例解释**
- $1 \leq \mathbf{T} \leq 100$。
- 对所有 $i$ 和 $j$，$\mathbf{A}_{ij}$ 只可能为 $\#$、$\mathbf{.}$、大写字母 $\mathbf{M}$ 或大写字母 $\mathbf{N}$。
- 恰好有一对 $i$ 和 $j$ 使得 $\mathbf{A}_{ij} = \mathbf{M}$。
- 恰好有一对 $i$ 和 $j$ 使得 $\mathbf{A}_{ij} = \mathbf{N}$。
**测试点 1（19 分，公开）**
- 时间限制：30 秒。
- $1 \leq \mathbf{R} \leq 10$。
- $1 \leq \mathbf{C} \leq 10$。
**测试点 2（30 分，隐藏）**
- 时间限制：120 秒。
- 最多 10 个测试用例满足：
- $1 \leq \mathbf{R} \leq 100$。
- $1 \leq \mathbf{C} \leq 100$。
- 其余测试用例满足：
- $1 \leq \mathbf{R} \leq 50$。
- $1 \leq \mathbf{C} \leq 50$。
由 ChatGPT 4.1 翻译