DWITE Online Computer Programming Contest, October 2010, Problem 5

That vacuum robot from Problem 2 did not work out that well – its breaks don't work. Luckily it safely stops whenever it hits a wall, so maybe it's not all that bad? We can use software to plan out shortest routes to bounce around from one spot to another, in a ~10~ by ~10~ room.

• # – walls
• . – empty space
• A – start position
• B – end position

The input will contain 5 sets of inputs, each a ~10~ by ~10~ room as described above. For a visual break in test cases, there will be an additional line of ~10~ dashes after every input set.

The output will contain 5 lines, each an integer of the minimum number of moves necessary to get from point ~A~ to point ~B~.

Notes: test cases will be such that it's always possible to come to a stop at point ~B~. The solution requires a stop, not simply a pass over the point. A robot can move in any of the 4 directions, and will continue moving until hitting a wall or an edge of the room.

Sample Input

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

Sample Output

4
3

Problem Resource: DWITE