DWITE '07 R5 #4 - Train ride

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, February 2008, Problem 4

You are trying to navigate a complicated train system to arrive at your destination in the quickest time possible. Given a system's schematic with start and end points, calculate the shortest length possible.

The schematic will be made up of a number of characters:

  • S - start point
  • E - end point
  • just about any other character - path connecting the stations

It doesn't really matter what character represents the path. Consider the schematic to be a 2D array where every character with the exception of space and x as a valid path point. Diagonal moves are allowed. So every point has 8 possible connection points, and that connection is made if both characters are valid.

The input will contain 5 sets of data -- N lines per set, 10 characters in length, each set separated by a line of characters x. 1 \le N \le 5. Each set represents a system schematic as described above.

The output will contain 5 lines -- a minimum travel length between S and E points.

Note: the dataset will contain a lot of whitespace, instead of typical dots. Make sure you can handle this data properly.

Sample Input

.-        
S   .-E   
 `-o      
xxxxxxxxxx
   -S---  
  `     ` 
  E     | 
  |     | 
  `-----` 
xxxxxxxxxx

Sample Output

6
3

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


Comments

There are no comments at the moment.