DWITE '07 R4 #4 - Shortest path around

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 2008, 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 file will contain five sets of data, each a 10 by 10 character matrix. There will be a line of 10 dashes after each set, to visually delimit sets of data. The character representations are as follows:

  • . - empty space
  • # - wall
  • X - one of the ends

The output will contain five lines -- each an integer distance between the two points marked with X.

There will always be only two X spots per set. There will always be a valid path. Valid steps are into any adjacent empty space; diagonal steps are legal. Refer to sample data for examples.

Sample Input

..........
..........
..........
....#.....
....#.....
X...#...X.
....#.....
....#.....
..........
..........
----------
..........
..........
........#.
........#.
X...#####X
...#......
..#.......
..........
..........
..........
----------

Sample Output

8
9

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


Comments


  • 1
    goatMan  commented on Aug. 29, 2020, 6:55 p.m.

    Why do I get Java array index out of bounds exception? Can someone help me out?


    • 1
      YaySushi  commented on Aug. 29, 2020, 10:44 p.m.

      line 122, should be x + 1, not x - 1