## DWITE '07 R5 #4 - Train ride

View as PDF

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 possible connection points, and that connection is made if both characters are valid.

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

The output will contain 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`