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
The input will contain x
.
The output will contain 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