问题
有一个迷宫,里面有 1 启动并 2 目标。迷宫是由 H 行和 W 列矩形单元阵列。每个单元格都被指定为起点、目标、路径或障碍。 让 (r, c) 是 r-第行, c从左边算起第一个单元格。
您将获得一张迷宫地图。您必须在该地图中绘制从起始单元格到每个目标单元格的两条路径。 路径是一个单元格数组,从起始单元格开始到目标单元格结束,不包含障碍单元格,并且数组中的每对相邻单元格都是相邻的。 (a, b) 和 (c, d) 是相邻的,如果 |a-c|+|b-d|=1。 您绘制的路径必须满足以下条件。
- 每条路径必须包含尽可能少的单元数。 这意味着每条路径必须是从起点到每个目标的最短路径。
- 为了使路径可区分,除了起始单元格之外,每条路径不得有任何共同的单元格。
确定是否可以在给定的迷宫中做出满足条件的路径,如果可能,则显示迷宫中的路径。 阅读输入和输出部分了解详细格式。
输入
H W
s_{(1,1)}s_{(1,2)}…s_{(1,W)}
s_{(2,1)}s_{(2,2)}…s_{(2,W)}
:
s_{(H,1)}s_{(H,2)}…s_{(1,W)}
-
第一行,两个整数 H, W (1 \leq H, W \leq 50),给出了迷宫的大小。
-
关于以下内容 H 行,每行包含一个长度的字符串 W,给出了迷宫的地图。 的 i-th (1 \leq i \leq H) 行的 j-th (1 \leq j \leq W) 字符代表单元格 (i, j)。 各字符的含义如下。
.表示该细胞是途径细胞。#表示该单元格是障碍单元格。S表示该单元格是起始单元格。A表示该单元格是第一个目标单元格。B表示该单元格是第二个目标单元格。
保证该字符
S,A,B仅出现一次。 还保证每个目标至少有 1 路径。
输出
如果没有路径满足问题部分中的条件,则输出 1 行包含 NA.
如果存在满足条件的路径,则输出 H 每行包含的行 W 字符。 的 i-th (1 \leq i \leq H) 行的 j-th (1 \leq j \leq W) 输出中的字符应代表单元格 (i, j) 在迷宫里。 输出必须满足以下条件。
- 作为输入路径的单元格必须是以下之一
.,aorb. - 输入中作为起点、障碍物或目标单元格的单元格必须与输入中的字符相同。
- 应该能够到达目标单元格
A从起始单元格开始,按照相邻的a细胞。细胞数量a必须是达到目标的最小可能性。 - 应该能够到达目标单元格
B从起始单元格开始,按照相邻的b细胞。细胞数量b必须是达到目标的最小可能性。
换句话说,显示每个目标的路径 A, B 按字符 a, b。
如果有多个可能的答案,您可以选择其中之一。
确保在输出末尾插入换行符。
输入示例 1
5 5 ..#.. .B.A# ...#. ..... ..S#.
输出示例 1
..#.. .BaA# .ba#. .ba.. .bS#.
输入示例 2
2 3 SBA ...
输出示例 2
NA
目标单元格不是障碍物,因此到达目标的最短路径 A 只是 (1, 1) → (1, 2) → (1, 3)。
但是,该路径包含目标单元格 B,因此您无法避免在最短路径中使用公共单元格。
因此,你应该输出 NA.
输入示例3
5 5 ..#.. .B.A# .#.#. ..... ..S#.
输出示例 3
NA
输入示例 4
5 8 .#...#.. .#.#.#.. .S.#...B .#####A. ........
输出示例 4
.#bbb#.. .#b#b#.. aSb#bbbB a#####A. aaaaaaa.