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×N grid of
square cells (2≤N≤20), some being empty and some containing impassable haybales. Bessie starts in
the lower-left corner (cell 1,1) and wants to move to the upper-right corner (cell N,N). You can gui
de her by telling her a sequence of instructions, each of which is either "forward", "turn left 90 d
egrees", or "turn right 90 degrees". You want to issue the shortest sequence of instructions that wi
ll guide her to her destination. If you instruct Bessie to move off the grid (i.e., into the barn wa
ll) or into a haybale, she will not move and will skip to the next command in your sequence.Unfortun
ately, Bessie doesn't know if she starts out facing up (towards cell 1,2) or right (towards cell 2,1
). You need to give the shortest sequence of directions that will guide her to the goal regardless o
f which case is true. Once she reaches the goal she will ignore further commands.
The first line of input contains N.
Each of the NN following lines contains a string of exactly N characters, representing the barn. The
first character of the last line is cell 1,1. The last character of the first line is cell N, N.Eac
h character will either be an H to represent a haybale or an E to represent an empty square.
It is guaranteed that cells 1,1 and N,N will be empty, and furthermore it is guaranteed that there i
s a path of empty squares from cell 1,1 to cell N,N
On a single line of output, output the length of the shortest sequence of directions that will guide
Bessie to the goal, irrespective whether she starts facing up or right.
In this example, the instructions "Forward, Right, Forward, Forward, Left, Forward, Left, Forward, F
orward" will guide Bessie to the destination irrespective of her starting orientation.
1.“无论Bessie处于左下角时是头朝向上还是朝向左”根据英文原文“Bessie doesn't know if she starts out facing up (towards cell 1,2) or right (towards cell 2,1).”应为无论Bessie处于左下角时是头朝向上还是朝向右
2.漏了原题很重要的一点:"Once she reaches the goal she will ignore further commands."即如果Bessie已经到达终点，她会忽视以后的所有行为