P6474 [NOI Online #2 入门组] 荆轲刺秦王

本测试数据为脚造，欢迎提供 hack。 第 18 组数据卡了很多人，放于附件中供检查。

时隔数年，刺客荆轲再次来到咸阳宫，试图刺杀嬴政。 咸阳宫的地图可以描述为一个 $n$ 行 $m$ 列的矩形。在这里，我们规定每一行中从左到右为 $x$ 轴正方向，每一列中从下到上为 $y$ 轴正方向，左下角的点坐标为 $(1,1)$。矩形中的点可以分为 $4$ 种： 1. 起点，也就是荆轲的所在点，在地图中用字符 `S` 代表。 2. 终点，也就是嬴政的所在点，在地图中用字符 `T` 代表。 3. 卫兵，在地图中用一个正整数 $a_{i,j}$ 代表。在这里，一个卫兵 $(i,j)$ 可以观察到与他曼哈顿距离小于 $a_{i,j}$ 的点。也就是卫兵 $(i,j)$ 可以观察到所有满足 $|x-i|+|y-j|

无

无

#### 样例 1 解释 起点为 $(1,2)$，荆轲可以依次走到 $(1,3)$, $(2,4)$, $(3,5)$ 到达终点。 #### 样例 2 解释 起点为 $(2,8)$，荆轲可以依次走到 $(2,5)$, $(2,2)$, $(5,2)$，需要注意的是，即使最后一步到达终点，但因为终点在卫兵的观察范围之内，所以仍然需要隐身进入。 #### 数据范围与提示 对于测试点 $1\sim 6$：$n$, $m\le 10$，$c_1=c_2=0$，保证所需的最短时间不超过 $5$ 或者无解。 对于测试点 $7\sim 10$：$n$, $m\le 20$，$c_1=c_2=0$，保证 `T` 的位置不在任何一个卫兵的观察范围之中。 对于测试点 $11\sim 12$：$n$, $m\le 20$，$c_1=0$ 对于测试点 $13\sim 14$：$n$, $m\le 20$，$c_1$, $c_2 \le 5$。 对于测试点 $15\sim 16$：卫兵个数不超过 $350$。 对于所有测试点：$2\le n$, $m\le 350$，$1\le a_{i,j}\le 350$，$0\le c_1$, $c_2\le 15$，$1\le d\le 350$。 保证 `S` 的位置不在任何卫兵的观察范围中。