U559193 第三章：深入敌巢

#### 第三章：深入敌巢 $\,\,\,\,\,\,\,\,\,$ 自从上次发现隐藏的危机之后，跪求一死便一直防范着它。现在正好有空，它于是让一批丝光歇林蚁（兵蚁）（就是常见的腐木中生存的黑蚁）和黑细长蚁（兵蚁）守住巢穴，自己孤身一人到那个洞穴探索。\ $\,\,\,\,\,\,\,\,\,$ 跪求一死溜进洞穴的办法十分简单：改换自己的气味，吸引兵蚁过来，击杀一只兵蚁改换气味，把原气味移至洞穴外将敌人引开，自己大摇大摆的进入洞穴。这个办法的重点是利用蚂蚁分辨敌人同族使用气味和信息素的特点，有意模仿黑蟹蚁蛛（蚁蛛，善于模仿蚂蚁，也爱吃蚂蚁，蛛形纲，同时作为神树族驯养的和特化蚁同阶的野怪）\ $\,\,\,\,\,\,\,\,\,$ 通过刚才击杀的那只兵蚁，跪求一死可以分析出敌人属于小黑家蚁，回想以前和腐木中生活的丝光歇林蚁和海滩边的红歇林蚁联手围攻小黑家蚁群，想不到现在又遇到了。\ $\,\,\,\,\,\,\,\,\,$ 跪求一死即将靠近核心区，没想到一堆皇家兵蚁拦住了它，（跪求一死心想：皇家兵蚁，这蚁后挺聪明的，这一招可以防止有敌虫混成兵蚁来刺杀！真是狡猾！）它仔细打量这皇家兵蚁，看起来异化方向是增强头部与上颚，接近全异巨首蚁了，移动估计还行，可以用从背后偷袭的办法取胜，不过要先让它们迷失方向，范围越大越好。\ $\,\,\,\,\,\,\,\,\,$ 于是跪求一死释放了红歇林蚁异化获得的传染性蚁酸——“$甲酸（Hcooh）！$”（技能处添加花体），一下子击倒一大片敌人。\ $\,\,\,\,\,\,\,\,\,$ “危险，有敌虫袭击！”短时间聚集了大量兵蚁，跪求一死的气味瞒不住了！它哼了一声，又释放了技能想要突围：“$皇家兵蚁，现！$”没错，它也会召唤皇家兵蚁，作为血统纯正的异化赤火蚁，召唤出来的皇家兵蚁都是亢奋火蚁（火蚁刚成年时有一段亢奋时期，战意最强！）！亢奋火蚁和异化小黑家蚁缠斗了起来，它们的上颚只能对异化小黑家蚁造成轻伤，但尾针的毒素威力可强悍了！生物碱可造成无菌性脓疱的形成，溶水性蛋白质有毒，可破坏生物腺基。（不准确，此处赤火蚁作为异化火蚁，能力有修改）只要被亢奋火蚁蜇刺一下，不久就会死亡。\ $\,\,\,\,\,\,\,\,\,$ 跪求一死趁乱发动退化的蚁翅滑翔了出去（跪求一死是雄蚁且无心婚飞，保留着可以滑翔的蚁翅），它再次封堵了这里，撤退回了蚁巢。

$\,\,\,\,\,\,\,\,\,$ 已知$n^{2}$大小的巢穴，跪求一死从左上角进入，要到达右下角。跪求一死只能向上、左、下、右四个方向移动，每次只能移动一格。每格上可能有敌方兵蚁，用'#'表示，没有兵蚁，用'.'表示。有兵蚁处需要击杀该兵蚁才可以通过，为了安全，跪求一死要击杀最少的兵蚁通过。现在它派了放哨蚁知晓了兵蚁分布情况，它想让一只最聪明的放哨蚁帮他计算结果。

$\,\,\,\,\,\,\,\,\,$ 第$1$行$1$个正整数$n$，表示地图边长\ $\,\,\,\,\,\,\,\,\,$ 接下来$n$行，每行$n$个字符，表示这一行兵蚁分布情况

$\,\,\,\,\,\,\,\,\,$ 一行，一个整数表示最少需要击杀几只敌方兵蚁

$\,\,\,\,\,\,\,\,\,$ 样例解释（仅$input 1$）： ``` 01111 12122 12122 12222 11111 ``` $\,\,\,\,\,\,\,\,\,$ 如图，通过$dfs$得到的到达每一个点的最少击杀数，右下角为$1$\ $\,\,\,\,\,\,\,\,\,$ 数据范围：$1