Background

This testdata is handmade. Hacks are welcome.

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

Problem Description

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|<a_{i,j}$.
4. Empty ground, represented by the character . on the map.

Jing Ke’s normal movement is to move one grid per second to any of the eight 8-connected directions. As shown in the figure below, the middle point is Jing Ke’s current position, and every second, he can move to any of the other eight points.

Note that during normal movement, Jing Ke cannot step into any cell that has a guard or is observable by any guard. Of course, he also cannot leave the Xianyang Palace, meaning that at any time, Jing Ke’s coordinates $(x,y)$ must satisfy $1\le x\le m$ and $1\le y\le n$.

Jing Ke also has two skills: Invisibility and Teleportation.

1. Invisibility: In the next second, Jing Ke enters an invisible state. Guards cannot observe Jing Ke, and Jing Ke may enter cells within guards’ observable ranges, but he still cannot enter the cell where a guard stands. Note that this state lasts for only one second.
2. Teleportation: In the next second, Jing Ke’s moving distance becomes $d$, but he can only move in the four directions up, down, left, and right. That is, he can move to
   $(x+d,y)$, $(x-d,y)$, $(x,y+d)$, $(x,y-d)$.

In this problem, the two skills can be used at the same time, and there is no cooldown. That is, after using a skill once, you may use it again immediately. Both skills have usage limits, and you do not have to use all of them.

Now, given the map of Xianyang, compute the minimum time needed for Jing Ke to reach the King of Qin’s position. In addition, among solutions with the same time, Jing Ke wants the total number of times the two skills are used to be as small as possible. If both the time and the total skill usage are the same, Jing Ke wants the number of invisibility uses to be as small as possible.

Input Format

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.

Output Format

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.

5 4 0 0 5
. 1 T 1
. . . 2
. 1 . .
S . . .
1 . . .

3 0 0

8 6 2 3 3
. S . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
2 . 2 . 2 .
. . 1 . T .
3 . 1 . . 3

3 1 3

8 6 5 5 2
. S . . . .
. . . . . .
. . . . . .
1 1 3 2 . 1
2 3 2 2 1 3 
3 2 4 1 4 3 
2 6 1 5 T 2 
8 1 6 3 2 10

-1

Hint

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