P6474 [NOI Online #2 Junior] Jing Ke Assassinating the King of Qin

This testdata is handmade. Hacks are welcome. The 18th group of testdata trapped many people, and it is provided in the attachment for checking.

After several years, the assassin Jing Ke comes to the Xianyang Palace again, trying to assassinate Ying Zheng. The map of the Xianyang Palace can be described as a rectangle with $n$ rows and $m$ columns. Here, we define that in each row, from left to right is the positive direction of the $x$ axis, and in each column, from bottom to top is the positive direction of the $y$ axis. The coordinate of the bottom-left corner is $(1,1)$. Points in the rectangle can be divided into $4$ types: 1. The start point, where Jing Ke is located, represented by the character `S` on the map. 2. The end point, where Ying Zheng is located, represented by the character `T` on the map. 3. Guards, represented by a positive integer $a_{i,j}$. A guard at $(i,j)$ can observe points whose Manhattan distance to him is less than $a_{i,j}$. That is, the guard at $(i,j)$ can observe all points $(x,y)$ satisfying $|x-i|+|y-j|

The first line contains five integers $n$, $m$, $c_1$, $c_2$, $d$, meaning the map size is $n\times m$, the usage limit of invisibility is $c_1$, the usage limit of teleportation is $c_2$, and the teleport distance is $d$. Then follow $n$ lines, each with $m$ elements. Each element is the character `S`, `T`, `.`, or a positive integer $a_{i,j}$, representing a grid point. See the problem description for details.

If Jing Ke cannot reach the King of Qin’s position, output one line with $-1$. Otherwise, output one line with three integers $t$, $u_1$, $u_2$, representing the minimum required time, the number of invisibility uses, and the number of teleportation uses, in this order.

#### Sample 1 Explanation The start point is $(1,2)$. Jing Ke can move to $(1,3)$, $(2,4)$, $(3,5)$ in order to reach the end point. #### Sample 2 Explanation The start point is $(2,8)$. Jing Ke can move to $(2,5)$, $(2,2)$, $(5,2)$ in order. Note that even though the last step reaches the end point, since the end point is within a guard’s observable range, Jing Ke still needs invisibility to enter. #### Constraints and Hints For test points $1\sim 6$: $n$, $m\le 10$, $c_1=c_2=0$. It is guaranteed that the minimum required time does not exceed $5$, or there is no solution. For test points $7\sim 10$: $n$, $m\le 20$, $c_1=c_2=0$. It is guaranteed that the position of `T` is not within any guard’s observable range. For test points $11\sim 12$: $n$, $m\le 20$, $c_1=0$. For test points $13\sim 14$: $n$, $m\le 20$, $c_1$, $c_2 \le 5$. For test points $15\sim 16$: the number of guards does not exceed $350$. For all test points: $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$. It is guaranteed that the position of `S` is not within any guard’s observable range. Translated by ChatGPT 5