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