# DWITE Online Computer Programming Contest

## Blow your mind with 4th D

January 2009
Problem 5

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 has the same 5×5 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 a 2×2 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```