题目描述

输入格式

第一行为三个整数 n，m，K，分别表示地图的长和宽，以及最多能放置的炮塔数量。

接下来的 n 行，每行包含 m 个字符， ‘#’ 表示地图上原有的障碍， ‘.’表示该处为空地，数据保证在原地图上存在 S 到 T 的路径。

输出格式

输出在合理布阵下，喵星人采取最优策略后，会受到的最大伤害。

注意必须保证在布阵结束后喵星人仍然可以沿一条或以上的路径从起点 S 到达终点 T ，否则他们组织更大规模的侵略。

3 3 1
S.T
...
...

7

提示

【提示】

样例的一种最优布局方案如下

S#T
.X.
...

【数据范围】

对于 30%的数据，保证：

$1\le n,m\leq 6$

对于 100%的数据，保证：

$\min(n,m)\le 6$，$\max(n,m)\le 20$,1<=K<=15且从S到T的路径必定存在