The Rock

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.

2/2 Output For each map, output a single line containing the length of the shortest path according to the description above. Sample Input 2 88 ..X..... ........ ##.##... ........ ##.##... ##.##... ........ ..E..... 34 ..X. .##. .E.. Sample Output 15 11