DWITE '08 R4 #5 - Blow your mind with 4th D

View as PDF

Submit solution

Points: 7
Time limit: 1.0s
Memory limit: 64M

Problem types
DWITE Online Computer Programming Contest, January 2008, Problem 5

This should be fun – this is another one of the maze questions, but this round it's set in 4D. Woah! Alright, 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 a static 5 \times 5 and uses pound signs # for walls and periods . for empty spaces. A for start, 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 + staying in place (skip to next frame); as long as there is no wall in space being moved to, in the next frame. Here's an example of a 2 \times 2 maze:

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

The solution is: right, wait, down. Notice how in the first and last steps the maze closes down, forcing a move, while on the 2nd 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 will contain 5 sets. The first line will specify the number of frames to a maze 1 \le N \le 25. The next 5N lines will describe N frames of the maze, as explained above.

The output file will contain 5 lines – the shortest path from A to B.

Sample Input

7
#####
##.##
A...B
#####
#####
#####
##.##
#...B
#####
#####
#####
##.##
##..B
#####
#####
#####
##.##
#####
#####
#####
#####
##.##
....B
#####
#####
#####
##.##
....B
#####
#####
#####
##.##
....B
#####
#####
3
#####
#####
##A##
#####
#####
#####
#...#
#.#.#
#...#
#####
#####
#####
##B##
#####
#####

Sample Output

6
2

Problem Resource: DWITE

Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported

Comments

There are no comments at the moment.