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 pointE
- 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 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
Problem Resource: DWITE
Comments