P1374 Assault on the Undercity

Because of the shocking “Wrathgate poisoning incident,” in order to suppress the rebellion of the Royal Apothecary Society, after all diplomatic work was completed, Warchief Thrall led Xiao A through the portal to the Undercity to quell the uprising.

The map of the Undercity is an $n \times m$ grid of $0/1$. If $a_{i, j} = 1$, then position $(i, j)$ is an obstacle and cannot be traversed; if $a_{i, j} = 0$, then position $(i, j)$ is passable. Xiao A and Thrall start at $(x_1, y_1)$, and the Dreadlord starts at $(x_2, y_2)$. Xiao A’s goal is to reach the Dreadlord’s position. Thrall moves according to a specific route, which is a digit string composed of digits $0$ to $4$. At second $i$: - If the $i$-th digit (thinking of the digit string repeated infinitely) is $0$, Thrall stays still this second. - If it is $1$, Thrall moves up by one cell this second. - If it is $2$, Thrall moves down by one cell this second. - If it is $3$, Thrall moves left by one cell this second. - If it is $4$, Thrall moves right by one cell this second. If Thrall’s next position would be a wall or outside the maze, Thrall stays in place. The Dreadlord follows the same rule. (In other words, you can think of the digit string as repeating infinitely; at second $i$, take the $i$-th character of this infinite string.) Each second, Xiao A may choose one of the four directions (up, down, left, right) and move one cell in that direction, provided the destination is not a wall and not out of bounds; or Xiao A may stay in place. However, due to the strange environment in the Undercity, Xiao A can remain outside Thrall’s “aura” for at most $s$ consecutive seconds; if this limit is exceeded, Xiao A dies. The aura has effective radius $d$, meaning Xiao A receives Thrall’s aura effect only when the distance $\sqrt{(x-xx)^2+(y-yy)^2}$ between Xiao A and Thrall is less than or equal to $d$. If Xiao A leaves Thrall’s aura and then re-enters the effective area of the aura, the counter resets to zero the next time Xiao A leaves the aura. Xiao A wants to know the minimum number of seconds needed to reach the Dreadlord’s position.

The first line contains four integers $n, m, s, d$. The next $n$ lines each contain $m$ digits ($0$ or $1$) without spaces, representing the map of the Undercity. The next line contains four integers $x_1, y_1, x_2, y_2$ ($1 \le x_1, x_2 \le n$, $1 \le y_1, y_2 \le m$). The next line is a digit string describing Thrall’s movement. The next line is a digit string describing the Dreadlord’s movement.

Output a single integer on one line, the minimum time required.

Source: kiro, original. Constraints: For $100\%$ of the testdata, $1 \le n, m \le 50$, $0 \le s \le 1000$, $0 \le d \le 100$, $1 \le$ length of the digit string $\le 100$, $0 \le$ answer $\le 100$. Translated by ChatGPT 5