DWITE Online Computer Programming Contest

January 2008

Problem 4

Shortest path around

Sometimes an open field could be as much of a maze as narrow tunnels. Given an obstacle in an otherwise empty room, what is the shortest path around it?

The input file **DATA4.txt** will contain five sets of data, each a 10 by 10 character matrix. There will be a line of 10 dashes after each set to visually delimit sets of data. The character representations are as follows:

- . - empty space
- # - wall
- X - one of the ends

The output file **OUT4.txt** will contain five lines -- each an integer distance between the two points marked with X.

There will always be only two X spots per set. There will always be a valid path. Valid steps are into any adjacent empty space; *diagonal steps are legal*. Refer to the sample data for examples.

Sample Input (only first two sets given):

.......... .......... .......... ....#..... ....#..... X...#...X. ....#..... ....#..... .......... .......... ---------- .......... .......... ........#. ........#. X...#####X ...#...... ..#....... .......... .......... .......... ----------

Sample Output (only first two sets given):

8 9