Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB
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.
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.
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.
.
, a
or b
.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.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.
5 5 ..#.. .B.A# ...#. ..... ..S#.
..#.. .BaA# .ba#. .ba.. .bS#.
2 3 SBA ...
NA
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
.
5 5 ..#.. .B.A# .#.#. ..... ..S#.
NA
5 8 .#...#.. .#.#.#.. .S.#...B .#####A. ........
.#bbb#.. .#b#b#.. aSb#bbbB a#####A. aaaaaaa.