神勇的小田

Time Limit: 1000 ms

Memory Limit: 65535 ms

Description

小田本来是南京理工大学ACM集训队的队员,但由于武功高强,身体条件出色,被特种部队挖走,去执行一项不可能完成的任务……
小田潜入敌人的巢穴去夺回原本属于中华人民共和国的三鹿奶粉配方,任务眼看就要成功了,出口就在前面,可是狡猾的敌人把铁质的地面通上了高压电,幸好小田身手敏捷,他立刻跳到了一个很高的木箱子上。由于小田多年从事ACM活动,脑子十分好用。看到周围有许多木箱子,把箱子踢到就可以踩在箱子上走。他心中一算就知道自己能出去了。
我们现在可以这样描述这个问题。小田所在的屋子的地面可以看成由n*n的格子组成,地板上要么有箱子(深色),要么没箱子,箱子高用数字表示。E表示出口。小田现在就在某一个箱子上。小田现在可以做两件事: 1、如果小田所处的箱子旁边还有箱子,他可以从一个箱子移动到另一个箱子上,移动花费1步,不考虑箱子的高度。如图a所示: 2、小田可以用大力精钢腿踢到所站的箱子,条件是倒的方向上没有箱子没有墙,箱子就会向前覆盖等于箱子高的地面,小田顺势用林波微步移动到倒了的箱子上,共花费1步,如图b,c,d所示。倒了的箱子不能再立起来,也不能再向其他方向踢了。在倒的箱子上可以移动,也可以从倒的箱子上调到相邻的其他箱子。每走一格算一步。
作为晚辈的你一定钦佩小田的功夫了。我们虽然不可能有小田的武功,但头脑并不比小田差,假如当时你是小田,你能找到最短的出去的路吗?

Input

有多组输入输出 每组中 第一行输入三个数 n,i, j,n表示房间的是由n*n的地板组成。i, j表示小田的位置是第i行第j列。 然后输入n*n的矩阵,其中.表示地面数字表示有箱子及高度。E表示出口。 输入 0 0 0表示输入结束。

Output

每组输出各占一行,表示逃出房间的最少步数。

Sample Input

5 5 3
.2..E
...2.
4....
....4
..2..
0 0 0

Sample Output

18

Hint

Source

ZhangFan

提交代码