天佑的手稿：

那个阴雨连绵的冬季，我时常在夜里梦见一座名为拉莱耶的巨型海底城市…建筑物的结构与欧几里德几何学完全相悖…整个城市散发出强烈的不洁气息……第二年初春，我在祖宅中无意间发现了一本名为《死灵之书》的古籍，并了解到每晚在梦中听见的“Ph'nglui mglw'nafh Cthulhu R'lyeh wgah'nagl fhtagn!”，意为“在永恒的宅邸，拉莱耶中，长眠的克苏鲁候汝入梦”……

那年夏天，我在返回学校的途中经过了一座名为印斯茅斯的小镇，我怎么也不会想到，在那居住着一种名为“深潜者”的半人半鱼的不洁的生物，更不会想到，它们就来自我梦中拉莱耶…救命！它们就要来了…

此时的天佑感受到了不可名状的恐惧，san值骤降，无法进行思考。请你帮助天佑逃离这座不洁的小镇。

已知：

1.当然，深潜者的思维与人有着一些差别：天佑要在不碰到深潜者，且与深潜者相邻（正上、正下、左、右，四个位置为相邻）时，方可通过。（起点和终点也要相邻）     

2.每走一步天佑的san值便会下降1.（从1开始、3为终点，1—2—3为两步）

1.m，n：印斯茅斯的长，宽。（m,n<=30）

2.印斯茅斯的地图：#代表建筑物（不可通过），*表示深潜者，&代表通路

3.天佑初始的san值(san<=50)

注意：天佑从左上角出发，右下角为出口（起点出口都为&）。

1.可逃走：所有路径中san值的最大值（逃出后）

2.不可逃走：Cthulhu

尾声——我们还是错误的估计了深潜者，它们毫无抓天佑之意，静静地看着天佑走远….

天佑手稿最后的一页：我似乎听见了我祖父，祖父的祖父…在拉莱耶的宫殿中，在克苏鲁的身旁唱着赞歌，等待着正确的星象，等待着伟大的克苏鲁的苏醒。我将步入深海，与我的祖辈永远的生存于…

测试数据2

输入

10 10
& & *  *   *  & *   &  &  *
*  & &  &  *  & *   *   &  &
# &  *   & & & & &  #   #
*  & #   #  #  *  & &  #   &
& & *   #  & & &  *   *   &
& & *   #  # &  &  *  #   *
*  & &  *   & *  &   & *   #
*  & &  *   *  & *   &  &  *
*  *  &  &  *  *  *   *   *   *
*  *  *   & &  & &  & & &
50

输出

32

游畅2020