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

The output file OUT4.txt will contain five lines, each being 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 the sample data for examples.

Sample Input (2 of 5 sets shown):
........
....#...
....#...
A...#..B
....#...
....#...
........
........
......#.
......#.
......#.
......#.
A..####B
..#.....
.##.....
.##.....
		        
Sample Output (2 of 5 sets shown):
7
7