AT_code_festival_china_d Maze

你将在一个由 $H$ 行 $W$ 列组成的迷宫中寻找路径。迷宫包含一个起点和两个终点。每个位置可能是起点、终点、通路或障碍。地图的每个坐标 $(r, c)$ 表示从上到下第 $r$ 行、从左到右第 $c$ 列的单元格。 ### 输入格式 第一行包含两个整数 $H$ 和 $W$，表示迷宫的高度和宽度，满足 $1 \leq H, W \leq 50$。 接下来的 $H$ 行，每行是一个长度为 $W$ 的字符串，表示迷宫的地图： - `.` 表示该位置为通路。 - `#` 表示该位置是障碍。 - `S` 表示起点。 - `A` 表示第一个终点。 - `B` 表示第二个终点。 保证输入中的字符 `S`, `A`, `B` 各自出现一次，并且每个终点都至少有一条可行路径可以到达。 ### 输出格式 如果无法找到满足条件的路径，输出 `NA`。 如果找到符合条件的路径，输出 $H$ 行，每行包含 $W$ 个字符，表示迷宫状态： - 输入中的通路位置在输出中可以是 `.`、`a` 或 `b`。 - 输入中的起点、障碍和终点位置在输出中必须保持不变。 - 从起点到 `A` 的路径只能通过相邻的 `a` 单元格到达，并且使用的 `a` 单元格数量必须最少。 - 从起点到 `B` 的路径只能通过相邻的 `b` 单元格到达，并且使用的 `b` 单元格数量必须最少。 换句话说，用 `a` 和 `b` 标记分别从起点到 `A` 和 `B` 的两条最短路径。允许有多个解，你可以任选其一。 请确保输出的最后有一个换行符。 ### 数据范围与提示 迷宫中指定了 $1$ 个起点和 $2$ 个终点。你需要画出从起点分别到达每个终点的最短路径。路径指从起点延伸到终点的单元格序列，且不穿过任何障碍，每对相邻的单元格都是相连的。 路径必须满足以下条件： - 每条路径是最短路径，也就是说，节点数量最少。 - 路径之间不能共享除起点外的任何单元格。 请判断是否能画出符合要求的路径，并输出这些路径。如果不能，则输出 `NA`。 ### 示例解释 例如，在某些情况下，终点 `A` 和 `B` 之间无法绘制两个不相交的最短路径，这时应输出 `NA`。 **本翻译由 AI 自动生成**

> $ 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)} $ - On the first line, two integers $ H $, $ W $ ($ 1\ \leq\ H,\ W\ \leq\ 50 $), the size of the maze is given. - On the following $ H $ lines, each line containing a string of length $ W $, the map of the maze is given. The $ i $-th ($ 1\ \leq\ i\ \leq\ H $) line's $ j $-th ($ 1\ \leq\ j\ \leq\ W $) character represents the cell $ (i,\ j) $. Each character means as following. - `.` represents that the cell is a pathway cell. - `#` represents that the cell is an obstacle cell. - `S` represents that the cell is the start cell. - `A` represents that the cell is the first goal cell. - `B` represents that the cell is the second goal cell. It is guaranteed that the character `S`, `A`, `B` appears only once. Also it is guaranteed that for each goal there's at least $ 1 $ path.

If there are no paths to fulfill the conditions in the problem section, output $ 1 $ line containing `NA`. If there are paths that fulfill the conditions, Output $ H $ lines that each line consists of $ W $ characters. The $ i $-th ($ 1\ \leq\ i\ \leq\ H $) line's $ j $-th ($ 1\ \leq\ j\ \leq\ W $) character in the output should represent the cell $ (i,\ j) $ in the maze. The output must fulfill the following conditions. - The cell that was a pathway in the input must be one of `.`, `a` or `b`. - The cell that was a start, an obstacle, or a goal cell in the input must be the same character as in the input. - It should be able to reach the goal cell `A` from the start cell by following the adjoining `a` cell. The number of cell `a` must be the least possible to reach the goal. - It should be able to reach the goal cell `B` from the start cell by following the adjoining `b` cell. The number of cell `b` must be the least possible to reach the goal. In other words, show the path to each goal `A`, `B` by the characters `a`, `b`. If there are more than one possible answers, you may choose any one of them. Make sure to insert a line break at the end of the output.

### Problem There is a maze which has $ 1 $ start and $ 2 $ goals. The maze is made of $ H $ rows and $ W $ columns rectangular array of cells. Each cell is specified as start, goal, pathway, or an obstacle. Let $ (r,\ c) $ be the $ r $-th row's, $ c $-th cell from the left. You will be given a map of the maze. You have to draw two paths from start cell to each goal cell in that map. A path is an array of cells that begins with start cell and ends with goal cell, contains no obstacle cell, and each pair of neighboring cells in the array is adjoining. A pair of cells $ (a,\ b) $ and $ (c,\ d) $ is adjoining if $ |a-c|+|b-d|=1 $. The paths you draw must fulfill the following conditions. - Each path must contain the least possible number of cells. **That means each path must be the shortest path from start to each goal.** - To make paths distinguishable, each path must not have any cell in common, except the start cell. Determine if you can make the paths that meets the condition in the given maze, and show the paths in the maze if possible. Read the Input and Output section for the detailed format. ### Sample Explanation 2 The goal cell is not an obstacle, so the shortest path to the goal `A` is only $ (1,\ 1) $ → $ (1,\ 2) $ → $ (1,\ 3) $. However, that path contains the goal cell B and thus you cannot avoid to use the common cell in the shortest paths. Therefore, you should output `NA`.