← 返回题目列表

AtCoder · code_festival_china_d

D. 迷宫

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

问题

有一个迷宫,里面有 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) 在迷宫里。 输出必须满足以下条件。

  • 作为输入路径的单元格必须是以下之一 ., a or b.
  • 输入中作为起点、障碍物或目标单元格的单元格必须与输入中的字符相同。
  • 应该能够到达目标单元格 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.