DWITE Online Computer Programming Contest
January 2009
Problem 5
Blow your mind with 4th D

This should be fun -- this is another one of the maze questions, but this round it's set in 4D. Woah! All right, don't freak out -- the depth is a constant 1, so you could think of it as a typical 2D maze that changes over time.

Each maze is has the same 5x5 size, using pound signs (#) for walls, periods (.) for empty spaces, A for start, and B for exit. Each time a step is made, the maze changes to the next frame as specified in the input file. The valid directions are up/down, left/right, and staying in place (skip to next frame), as long as there is no wall in the space being moved to in the next frame. Here's an example on 2x2 maze:

4 frames
A# #. #. ##
## ## ## #B
  

The solution is: right, wait, down. Notice how in the first and last steps the maze closes off the current cell thus forcing a move, while on the second step one must wait for a new path to open up. The entire maze expires as the frames end, so 4 - 1 = 3 is the maximum number of steps to a solution.

The input file DATA5.txt will contain 5 sets. The first line will specify the number of frames to a maze, 1 <= N <= 25. The next N*5 lines will describe N frames of the maze as explained above.

The output file OUT5.txt will contain 5 lines -- the length of the shortest path from A to B.

Sample Input (2 of 5 shown):
7
#####
##.##
A...B
#####
#####
#####
##.##
#...B
#####
#####
#####
##.##
##..B
#####
#####
#####
##.##
#####
#####
#####
#####
##.##
....B
#####
#####
#####
##.##
....B
#####
#####
#####
##.##
....B
#####
#####
3
#####
#####
##A##
#####
#####
#####
#...#
#.#.#
#...#
#####
#####
#####
##B##
#####
#####
		        
Sample Output (2 of 5 shown):
6
2