# DWITE Online Computer Programming Contest

## Train ride

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 is 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 file DATA4.txt will contain 5 sets of data – N lines per set, 10 characters in per line, and each set being terminated by a line of ‘x’ characters. 1 ≤ N ≤ 5. Each set represents a system schematic as described above.

The output file OUT4.txt will contain 5 lines – the 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 (only first two sets shown):
``` .-
S   .-E
`-o
xxxxxxxxxx
-S---
`     `
E     |
|     |
`-----`
xxxxxxxxxx```
Sample Output (only first two sets shown):
```6
3```