[Usaco2017 Jan]Cow Navigation

时间限制：10s 空间限制：128MB

题目描述

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.

给定一个N*N的网格(N<=20)，你从左下角出发，要到达右上角，网格中会有障碍物你要给定一个长度最短的行为序

列（往前走，左转，右转），使得无论Bessie处于左下角时是头朝向上还是朝向左都可以在执行完这个序列后到达

右上角如果当前的行为会导致Bessie走到障碍物上或者越界，则Bessie会忽视这个行为

输入格式

The first line of input contains N.

第一行为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.

接下来N行每行N列，描述这个网格，H表示障碍物，E表示空地

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.

输出最短命令序列的长度

样例输入

3
EHE
EEE
EEE

样例输出

9
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.
当Bessie在左下角的时候，执行前进，右转，前进，前进，左转，前进，左转，前进，前进无论Bessie一开始是朝
向上还是朝向下，都可以到达右上角。

提示

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已经到达终点，她会忽视以后的所有行为

题目来源

Gold