Cow Navigation#10552
Bessie has gotten herself stuck on the wrong side of Farmer John's barn again, and since her vision is so poor, she needs your help navigating across the barn.
The barn is described by an n \times n grid of square cells, some of which are empty and some of which contain impassable haybales. Bessie starts in the lower-left corner (cell ) and wants to reach the upper-right corner (cell ). You can guide her by giving her a sequence of instructions, each of which is either "forward", "turn left degrees", or "turn right degrees". You want to give her the shortest possible sequence of instructions that will guide her to her destination.
If you instruct Bessie to move off the grid (i.e., into the barn wall) or into a haybale, she will not move and will simply proceed to the next command in the sequence.
Unfortunately, Bessie does not know whether she starts out facing up (towards cell ) or right (towards cell ). You need to give her the shortest possible sequence of instructions that will guide her to the goal regardless of which starting orientation is correct. Once she reaches the goal, she will ignore any remaining commands.
The first line contains n~(2 \le n \le 20). Each of the following lines contains a string of exactly characters, representing the barn. The first character of the last line represents cell , while the last character of the first line represents cell .
Each character is either , representing a haybale, or , representing an empty cell.
It is guaranteed that cells and are empty. Furthermore, there is guaranteed to be a path consisting entirely of empty cells from cell to cell .
Print the length of the shortest sequence of instructions that will guide Bessie to the goal regardless of whether she starts facing up or right.
In this example, the sequence of instructions "Forward, Right, Forward, Forward, Left, Forward, Left, Forward, Forward" will guide Bessie to the destination regardless of her starting orientation.
Example 1