DWITE Online Computer Programming Contest, January 2009, Problem 4

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 will contain five sets of data, each an ~8 \times 8~ character map. The character representations are as follows:

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

The output 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

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

Sample Output

7
7

Problem Resource: DWITE