Problem 1072 --妹妹与怪兽

1072: 妹妹与怪兽

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 89  Solved: 15
[Submit][Status][Web Board][Creator:]

Description

怪兽突然出现啦!都市里最强的妹妹拿上了最新武器去打怪兽。

他们可以看作处在一张 n×n 的平面地图上,图的正上方为实际的正北方(N)。

其中 '.' 表示可以通过的街道, '#' 表示不能通过的摩天大楼等障碍物。

都市的规划非常规则,妹妹只能向东南西北四个方向移动(E/S/W/N) 

但是最新武器就不一样了,他会持续地向八个方向发射死亡光线(DEATH BEAM),即 E/S/W/N/SE/SW/NE/NW 

并且他非常地智能,向每个方向发射的光线一定会停在最近的障碍物之前!

因为妹妹的年纪还很小,所以每个时刻只能移动一步。

而怪兽就比较蠢了,它根本不会动。

现在其他的妹妹很想知道最快哪个时刻能够消灭怪兽!

Input

多组数据,不超过10组。

每组数据第一行一个整数 n,表示地图的大小为 n×n,不超过 700

接下来 n 行给出地图,其中 'S' 表示妹妹0时刻所在的位置(SISTER'S POSITION),'M' 表示怪兽0时刻所在的位置 (MONSTER'S POSITION)。'.' 和 '#' 如上所述。

Output

一行一个整数,表示最快打死怪兽的时刻。

若不能打死,请输出 -1 

Sample Input

5
S...#
.#...
.....
.....
....M
5
M.#..
..#..
..#..
..#..
..#.S

Sample Output

4
-1

HINT

0时刻的时候,因为有障碍物的存在,死亡光线打不到怪兽。妹妹有三种路线使得4时刻能打死怪兽。
① E-E-S-S
② S-S-E-E
③ S-S-S-S

Source

[Submit][Status]