喵星人入侵地球：留学生特工揭露阴谋，地球防御小组制定反侵略计划

喵星人入侵地球：留学生特工揭露阴谋，地球防御小组制定反侵略计划

我有幸被选为从地球到猫星球的留学生。我实际上是在充当特工，调查猫们是否有入侵地球的意图。猫真的计划入侵地球！从他们口中得到确切消息后，地球小队成员决定制定反入侵计划。

猫到达地球的唯一途径可以看作是一个n×mn\times mn×m的网格点。猫们将从地图上的SSS位置出发，目的地是地球的入口TTT。为了抵御猫的入侵，地球防卫队计划在地图上的网格点上放置一些炮塔（最多三K党）。炮塔会攻击周围888个方向（888个方向为：东、南、西、北、东北、西北、东南、西南）（如下图，中间格子的炮塔可以攻击周围8个格子） ）。此外，地球防卫队还可以在地图上放置无限的障碍物，让猫无法通过障碍网格。

右图是一个 3×33\times 33×3 地图的例子，其中 X\tt XX 代表炮塔，#\tt \## 代表障碍物，猫无法通过有炮塔或障碍物的网格。在这张地图中，猫从SSS走到TTT时受到的伤害如下：

所以受到的总伤害为2+3+2=72+3+2=72+3+2=7。

作为地球防卫队的一员，请为猫们安排好阵型，让猫们受到最大的伤害。请注意，如果从 SSS 到 TTT 有多条路径，喵会选择伤害最小的一条。