DWITE '08 R3 #5 - Now in 3D

View as PDF

Submit solution

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

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
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 2 \le n \le 5 followed by n*n 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 A and 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 2*2*2 empty cube, with A and B in two opposite corners. There are 6 different ways to get from A to B in 3 steps. There are also 3 different ways to get from A to 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 2*2*2 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 3*3*3 cube. A and B are on empty layers, but they are separated by a mostly filled layer, with a single opening in its "bottom-right" corner.

Sample Input

2
A.
..
..
.B
2
A.
##
#.
#B
3
A..
...
...
###
###
##.
B..
...
...

Sample Output

3
3
10

Attribution-NonCommercial-ShareAlike 3.0 Unported (CC BY-NC-SA 3.0) Problem Resource: DWITE


Comments

There are no comments at the moment.