P16295 [蓝桥杯 2026 省 Java A 组] 勇闯迷宫

有一个 $n \times m$ 的迷宫，迷宫中的每个格子是以下四种类型之一： - `#`：墙，不能进入； - `.`：空地，可以进入； - `S`：起点； - `T`：终点。 其中，`S` 和 `T` 各恰好出现一次，且都视为可通行格子。 除了格子类型外，每个格子 $(x, y)$ 还对应一个整数 $col_{x,y}$。对于可通行格子，这个整数表示该格子的属性，满足 $0 \le col_{x,y} < P$；如果该格子是墙，则对应的整数没有实际作用，可以忽略。 迷宫中还存在一个会随时间变化的环境属性 $p$，它的取值范围同样是 $0 \sim (P - 1)$。初始时，$p = 0$。 小蓝一开始位于起点 `S`。时间按秒进行。每经过 1 秒，小蓝必须执行恰好一个动作：向上、下、左、右移动一格，或者留在原地不动。移动时不能走出迷宫，也不能进入墙。 在每一秒中，事件按如下顺序发生： 1. 小蓝先执行这一秒的动作； 2. 接着根据这一秒结束时所在格子的属性，与当前环境属性 $p$ 进行比较： - 如果两者相同，则这一秒不会受到伤害； - 如果两者不同，则这一秒会受到 1 点伤害； 3. 最后更新环境属性： $$ p = (p + 1) \bmod P $$ 需要注意的是，小蓝刚开始站在起点时，不会立刻进行伤害判定。第一次判定发生在第一秒动作结束后。若某一秒动作结束后小蓝到达终点 `T`，则这一秒的伤害仍需正常结算，结算完成后才算到达终点。 此外，小蓝在整个过程中最多可以使用一次技能，也可以不使用。使用技能时，会额外产生 1 的代价，并且可以将当前环境属性 $p$ 直接改为任意一个 $0 \sim (P - 1)$ 之间的值。 整个过程中产生的总代价由两部分组成： - 每次受到伤害产生的代价； - 使用技能产生的代价。 现在，请你计算，小蓝从 `S` 到达 `T` 的最小总代价。若无法到达终点，输出 `-1`。

第一行包含三个整数 $n, m, P$。 接下来 $n$ 行，每行一个长度为 $m$ 的字符串，表示迷宫。 再接下来 $n$ 行，每行包含 $m$ 个整数，表示各个格子的 $col_{x,y}$。

输出一个整数，表示最小总代价。若无法到达终点，输出 `-1`。

### 【样例说明】 初始时环境属性 $p = 0$。 先在起点停留 1 秒。此时小蓝所在格子的属性为 0，与当前环境属性相同，所以这一秒不会受到伤害。之后环境属性更新为 1。 接下来依次向下、下、右、右、右移动到终点。每一秒结束时，小蓝所在格子的属性都恰好等于当时参与判定的环境属性，因此整个过程中都不会受到伤害。 同时不使用技能，所以总代价为 0。 ### 【评测用例规模与约定】 对于 $30\%$ 的评测用例，$1 \le n, m \le 30$，$2 \le P \le 3$。 对于额外 $30\%$ 的评测用例，$2 \le P \le 10$。 对于所有的评测用例，$1 \le n, m \le 300$，$2 \le P \le 100$。