8463: Cow Navigation

内存限制:128 MB 时间限制:1 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:0 通过:0

题目描述

贝西误把自己困在了FJ谷仓的一侧。因为她的视力很差,她在脱困时需要你的帮助。

谷仓的平面图由一个方形细胞图(即所画图)呈现,有些细胞(即单位)是空的,其他的则是不可通过的柴草堆。贝西从左下角开始(细胞1,1)想一路搬到右上角。你可以引导她,告诉她一个指令序列,指令可以为“前进”“左转90度”“右转90度”。你需要得出能够使她到达目的地所用的最短指令序列。如果你指示贝西离开谷仓或至柴草堆,她不会移动,会直接跳到下一个命令序列。

不幸的是,贝西不知道她一开始所朝的方向(可能是上或右),而序列无需考虑这种情况,(使得bessie无论是朝上还是朝右,根据给出的指令都能到达终点。)

注意:到了终点就不会再移动了

输入格式

The first line of input contains N

Each of the N 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.

Each 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 is 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