Problem D
The Rock
Input: standard input
Output: standard output
Time Limit: 12 seconds
Memory Limit: 32 MB
A group of terrorists have taken hostages on the
former prison island Alcatraz (now a tourist attraction)
outside San Francisco, and is
demanding a big ransom from the US
government. If they are not paid within 40 hours, they will launch 15 rockets
of V.X. poison gas at San Francisco,
each rocket capable of killing 70,000 people.
The Pentagon is planning on sending a SEAL team
to Alcatraz to destroy the rockets. They intend to
penetrate the island through the tunnels under the prison building, but because
the prison has been rebuilt so many times, all the maps of the tunnels are
useless. The only man who can help them is John Mason, a former inmate who once
successfully escaped from Alcatraz through the tunnels.
However, Mason is getting old so he doesn't
remember all the details of the tunnels. More precisely, he knows that there is
exactly one wall whose location he doesn't remember. Since they're running out
of time, they want to make sure that they take a path which will guarantee the
shortest possible time to reach the exit of the tunnels no matter where this
extra wall is. Since you're the top program writer at the Pentagon, it's your
job to write the program to find this shortest path!
For simplicity, we can assume that the tunnels
below Alcatraz can be described as a rectangular grid,
where each grid square is either wall or open space, and walking is permitted
only between adjacent non-wall squares. Two squares are adjacent if they have
one side in common. The additional, unknown, wall occupies exactly one square,
and the team will not notice this wall until they've reached an adjacent square
to it.
Example:
..X.....
........
##.##...
........
##.##...
##.##...
........
..E.....
If
the team walks straight ahead from the entrance (E), they may face a wall at
row 4 column 3, in which case they have to turn around and the length of the
path will be 17. It's better to walk to the right immediately, as this will
ensure a path of length at most 15.
Input
The
first line in the input will contain one integer n (n ≤ 10) which
is the number of maps to process. Then follows the n map descriptions.
Each
map description starts with a blank line, followed by a line with two integers,
describing the number of rows and columns in the map, respectively. The map
then follows one row on each line. '#' is used for walls, '.' for
open space, 'E' is the entrance and 'X' is the exit. The number
of rows and columns in the map is at least 3 and at most 40.
You
may assume that the map is valid and that there will be exactly one entrance
and one exit square. You may also assume that there exist at least two disjoint
paths (sharing no squares except the entrance and exit) from the entrance to
the exit and that the additional wall will neither be on the entrance nor exit
square.
Output
For
each map, output a single line containing the length of the shortest path
according to the description above.
Sample Input
2
8 8
..X.....
........
##.##...
........
##.##...
##.##...
........
..E.....
3 4
..X.
.##.
.E..
Sample Output
15
11
(Regionals 2002 Warm-up Contest, Problem setter: Jimmy Mårdell)