Problem M
Eye Spy
Now that they have blaze rods and some ender pearls, Alex needs to meet her friends at the end portal. Thankfully, she is already by the stronghold, and her friends gave her a map showing where the portal is inside of it so that she does not need to wander around searching for it. However, the map is large and Alex is having a hard time determining how to actually get to the portal.
Can you help Alex identify the path to the portal?
Input
The input begins with a line containing two integers, $r$ and $c$, where $r$ is the number of rows in the map, and $c$ is the number of columns.
The next $r$ lines each contain $c$ characters. These lines collectively describe the map.
The map contains the following characters:
-
’A’ - Alex’s current position
-
’P’ - the location of the portal
-
’.’ - an open square that Alex can traverse
-
’#’ - a wall
Alex can move to adjacent squares, but not diagonally.
You are given that $4 \le r,c \le 400$. Also, the edges of the map are all walls. The stronghold is set up so that there is at most one path between any two open squares.
Output
If there is no path between Alex and the portal, output ’call for help’.
Otherwise, draw the shortest path between Alex and the portal on the map by replacing each open square along the path with the letter ’X’.
| Sample Input 1 | Sample Output 1 |
|---|---|
5 7 ####### #....A# ##.#.## #P.#..# ####### |
####### #.XXXA# ##X#.## #PX#..# ####### |
| Sample Input 2 | Sample Output 2 |
|---|---|
11 11 ########### #.#.#..#.A# #...#.##.## ##.#.....## #....##.#.# #.#.#...#P# #.#..#.#..# #.#.#..#.## ##..#.#...# #..#....#.# ########### |
########### #.#.#..#XA# #...#.##X## ##.#...XX## #....##X#.# #.#.#.XX#P# #.#..#X#XX# #.#.#XX#X## ##..#X#XX.# #..#.XXX#.# ########### |
| Sample Input 3 | Sample Output 3 |
|---|---|
10 10 ########## #..#...#.# #.#..#.#.# #...#....# #.#..#.#.# ##.#.P#.## #....#A..# #.#.#..### #.#..#...# ########## |
call for help |