P2337 [SCOI2012] 喵星人的入侵

题目描述

a180285 幸运地被选作了地球到喵星球的留学生,其实是作为特工去调查,喵星人是否有侵略地球的企图。喵星人果然打算入侵地球!从 a180285 口中得到确切消息之后,地球小组成员决定制定反侵略计划。 喵星到地球的一段必经之路可以看作 $n\times m$ 的格点,喵星人将会从地图上的 $S$ 位置出发,目的地是地球的入口 $T$。为了抵抗喵星人的入侵,地球防御小组打算在地图上的格点上放置一些炮塔(最多放置 $K$ 个),炮塔攻击周围的 $8$ 个方向($8$ 个方向分别是:东、南、西、北、东北、西北、东南、西南)(如下图所示,中间格子的炮塔可以攻击周围的八个格子)。此外地球防御小组还可以在地图上放置无限多个障碍,使得喵星人无法从有障碍的格子经过。 ![](https://cdn.luogu.com.cn/upload/image_hosting/l6ezyb3h.png) 右图是 $3\times 3$ 地图的一个示例,其中 $\tt X$ 表示炮塔,$\tt \#$ 表示障碍,有炮塔或者障碍的格子,喵星人都无法经过。在这张地图中喵星人从 $S$ 走到 $T$ 受到的伤害如下: - 在 $S(1, 0)$ 处受到伤害为 $2$(炮塔 $(0,0)$ 和 $(2, 1)$ 能攻击到 $S$); - 在空地 $(1,1)$ 处受到伤害为 $3$(同时被炮塔 $(0,0),(0,2)$ 和 $(2, 1)$ 攻击); - 在 $T(1,2)$ 处受到伤害为 $2$(炮塔 $(0,2)$ 和 $(2, 1)$ 能攻击到 $T$)。 于是受到的总伤害为 $2+3+2=7$。 作为地球防御小组的成员,请你为喵星人布阵,使得喵星人受到的伤害最大。注意如果有多条从 $S$ 到 $T$ 的路径,喵星人会选择伤害最小的一条。

输入格式

输出格式

说明/提示

### 样例解释 样例的一种最优布局方案如下: ```plain S#T .X. ... ``` ### 数据范围及约定 - 对于 $30\%$ 的数据,保证 $1\le n,m\leq 6$; - 对于 $100\%$ 的数据,保证 $\min(n,m)\le 6$,$\max(n,m)\le 20$,$1\le K\le 15$ 且从 $S$ 到 $T$ 的路径必定存在。