BYU Algorithm Challenge 5.0

PacMan was popular many years ago, but now he’s old and can’t eat like he used to. These days he has rheumatism and just wants to find the quickest way out of each maze without getting eaten by a ghost. Luckily, the ghosts are older too (and lazy). They simply stake out key areas in each maze, hoping that PacMan will run into them accidentally. Of course, if PacMan eats a power pellet before hitting a ghost, it’s the ghost that will be eaten. But the ghosts are lazy, and it’s a risk they’re willing to take.

Write a program that determines the least number of moves PacMan must make to reach the exit of each maze without being eaten. Each move is either one unit up, down, left, or right; PacMan doesn’t have the dexterity to move diagonally. 

The input will consist of up to 20 square mazes of dimension 4x4 to 10x10. The first line of the input file will contain an integer indicating the total number of mazes in the input. For each maze, there will be a single line containing an integer, n, indicating the size of the maze (n x n). The next n lines represent the maze and will contain n characters each. Possible characters for each maze are:

‘C’ PacMan’s starting position. Each maze will contain exactly one.
‘X’ Exit. Each maze will contain exactly one, and it is PacMan’s goal to reach it.
‘#’ Wall. This is impassible. The outside of each maze will always be surrounded by walls, but they can appear inside the maze as well.
‘A’ Ghost. Each maze will contain 0 to 4 ghosts. They do not move, and PacMan cannot pass them unless he eats (passes over) a power pellet first.
‘@’ Power pellet. PacMan may pass through these, and if he does then he can pass through ghosts freely for the remainder of his moves in this maze. Each maze will contain 0 to 4 power pellets.
‘.’ Empty space. This is a regular passable space. It has no special significance. 

If PacMan can get to the exit, print the message, “PacMan can escape in <X> moves.” Replace <X> with the minimum number of moves required for PacMan to escape. If PacMan cannot get to the exit, print the message, “PacMan should retire.”