DWITE Online Computer Programming Contest

January 2009

Problem 4

Shortest path around v2

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 8 by 8 character map. The character representations are as follows:

- . - empty space
- # - wall
- A - start
- B - end

The output file **OUT4.txt** will contain five lines -- each the shortest integer distance between A and B.

*Notes:* There will always be a
valid path. Valid steps are into any adjacent empty space; *diagonal steps are valid*. Refer to sample data for examples.

Sample Input (2 of 5 sets shown):

........ ....#... ....#... A...#..B ....#... ....#... ........ ........ ......#. ......#. ......#. ......#. A..####B ..#..... .##..... .##.....

Sample Output (2 of 5 sets shown):

7 7