DWITE '08 R4 #4 - Shortest path around v2

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, January 2009, Problem 4

Sometimes an open field could be as much of a maze as narrow tunnels. Given an obstacle in an otherwise empty room, what is the shortest path around it?

The input will contain five sets of data, each a 8 by 8 character map. The character representations are as follows:

  • . - empty space
  • # - wall
  • A - start
  • B - end

The output will contain five lines -- each the shortest integer distance between A and B.

Notes: There will always be a valid path. Valid steps are into any adjacent empty space; diagonal steps are valid. Refer to sample data for examples.

Sample Input

........
....#...
....#...
A...#..B
....#...
....#...
........
........
......#.
......#.
......#.
......#.
A..####B
..#.....
.##.....
.##.....

Sample Output

7
7

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


Comments

There are no comments at the moment.