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:
- . – empty space
- # – wall
- A – start
- B – end
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