P16295 [Lanqiao Cup 2026 NOI Qualifier Java Group A] Brave the Maze.

There is an $n \times m$ maze. Each cell in the maze is one of the following four types: - `#`: a wall, cannot enter; - `.`: empty ground, can enter; - `S`: the start; - `T`: the target. `S` and `T` each appear exactly once, and both are considered passable cells. In addition to the cell type, each cell $(x, y)$ corresponds to an integer $col_{x,y}$. For a passable cell, this integer represents the cell's attribute and satisfies $0 \le col_{x,y} < P$. If the cell is a wall, the integer has no actual use and can be ignored. There is also an environment attribute $p$ in the maze that changes over time. Its range is also $0 \sim (P - 1)$. Initially, $p = 0$. Xiao Lan starts at `S`. Time is counted in seconds. Every 1 second, Xiao Lan must perform exactly one action: move one cell up, down, left, or right, or stay in place. When moving, Xiao Lan cannot leave the maze and cannot enter a wall. In each second, events happen in the following order: 1. Xiao Lan performs the action for this second; 2. Then compare the attribute of the cell where Xiao Lan is located at the end of this second with the current environment attribute $p$: - If they are the same, Xiao Lan takes no damage in this second; - If they are different, Xiao Lan takes 1 point of damage in this second; 3. Finally, update the environment attribute: $$ p = (p + 1) \bmod P $$ Note that when Xiao Lan is initially standing on `S`, there is no immediate damage check. The first check happens after the action of the first second. If Xiao Lan reaches `T` at the end of some second, the damage for that second still must be settled normally, and only after the settlement is it considered that Xiao Lan has reached the target. Also, during the whole process, Xiao Lan may use a skill at most once, or not use it. When using the skill, it incurs an extra cost of 1, and it can directly change the current environment attribute $p$ to any value in $0 \sim (P - 1)$. The total cost during the whole process consists of two parts: - the cost caused by taking damage each time; - the cost caused by using the skill. Now, compute the minimum total cost for Xiao Lan to reach `T` from `S`. If the target cannot be reached, output `-1`.

The first line contains three integers $n, m, P$. The next $n$ lines each contain a string of length $m$, describing the maze. The next $n$ lines each contain $m$ integers, describing $col_{x,y}$ for each cell.

Output one integer, the minimum total cost. If the target cannot be reached, output `-1`.

### [Sample Explanation] Initially, the environment attribute $p = 0$. First, stay at the start for 1 second. At this time, the attribute of the cell where Xiao Lan is located is 0, which is the same as the current environment attribute, so Xiao Lan takes no damage in this second. Then the environment attribute is updated to 1. Next, move down, down, right, right, right to the target. At the end of each second, the attribute of the cell where Xiao Lan is located is exactly equal to the environment attribute used in the check at that time, so no damage is taken during the whole process. At the same time, the skill is not used, so the total cost is 0. ### [Constraints and Assumptions] For $30\%$ of the testdata, $1 \le n, m \le 30$, $2 \le P \le 3$. For another $30\%$ of the testdata, $2 \le P \le 10$. For all testdata, $1 \le n, m \le 300$, $2 \le P \le 100$. Translated by ChatGPT 5