DWITE Online Computer Programming Contest, December 2008, Problem 5
Let's try to break out from the confines of the over-simplified 2D problems, and add some depth to the otherwise typical maze problems.
The input will contain 5 sets of data. Each set starts out with a single integer followed by lines, describing a cube space. Pound sign (
#) for solid space; period (
.) for free space; capital "A" (
A) for start; capital "B" (
B) for end.
The output will contain 5 lines – each the shortest distance between
B in the input maze.
The maze traversal is done only though free space, in any of the 6 directions. There are no diagonal movements.
Sample input explanation; first set: is a empty cube, with
B in two opposite corners. There are 6 different ways to get from
B in 3 steps. There are also 3 different ways to get from
B in 7 steps (without backtracking), but since we are looking for the shortest distance, the latter is of less interest.
Sample input explanation; second set: is also a cube, but filled space forces only a single path to be available. Think of the path this way, starting at
A: right, up one layer, down. Also 3 steps.
Sample input explanation; third set: is a cube.
B are on empty layers, but they are separated by a mostly filled layer, with a single opening in its "bottom-right" corner.
2 A. .. .. .B 2 A. ## #. #B 3 A.. ... ... ### ### ##. B.. ... ...
3 3 10