P15674 [ICPC 2024 Jakarta R] X Aura

ICPC 山可以表示为一个有 $R$ 行（编号从 $1$ 到 $R$）和 $C$ 列（编号从 $1$ 到 $C$）的网格。位于第 $r$ 行第 $c$ 列的单元格记为 $(r, c)$，其高度为 $H_{r, c}$。如果两个单元格共享一条边，则它们是相邻的。形式化地，$(r, c)$ 与 $(r-1, c)$、$(r+1, c)$、$(r, c-1)$ 和 $(r, c+1)$ 相邻（如果它们存在）。 你只能在相邻单元格之间移动，并且每次移动都会产生一个**惩罚值**。当拥有一个正的奇数整数 $X$ 作为**光环**时，从一个高度为 $h_1$ 的单元格移动到一个高度为 $h_2$ 的单元格，你会受到 $(h_1 - h_2)^X$ 的惩罚。注意，惩罚值可以是负数。 你需要回答 $Q$ 个独立的场景。在每个场景中，你从起始单元格 $(R_s, C_s)$ 出发，希望以最小的总惩罚值到达目标单元格 $(R_f, C_f)$。在某些场景中，总惩罚值可能会变得任意小；这样的场景被称为**无效的**。请找出从起始单元格移动到目标单元格的最小总惩罚值，或者判断该场景是否无效。

第一行包含三个整数 $R$ $C$ $X$（$1 \leq R, C \leq 1000$；$1 \leq X \leq 9$；$X$ 是奇数）。 接下来的 $R$ 行，每行包含一个长度为 $C$ 的字符串 $H_r$。$H_r$ 中的每个字符都是 0 到 9 的数字。$H_r$ 的第 $c$ 个字符表示单元格 $(r, c)$ 的高度，即 $H_{r, c}$。 接下来一行包含一个整数 $Q$（$1 \leq Q \leq 100\,000$）。 接下来的 $Q$ 行，每行包含四个整数 $R_s$ $C_s$ $R_f$ $C_f$（$1 \leq R_s, R_f \leq R$；$1 \leq C_s, C_f \leq C$）。

对于每个场景，在一行中输出以下内容。如果该场景无效，输出 INVALID。否则，输出一个整数，表示从起始单元格移动到目标单元格的最小总惩罚值。

**样例输入/输出 #1 的解释** 对于第一个场景，其中一个解决方案是按如下路径移动：$(1, 1) \rightarrow (2, 1) \rightarrow (3, 1) \rightarrow (3, 2) \rightarrow (3, 3) \rightarrow (3, 4)$。该方案的总惩罚值为 $(3 - 4)^1 + (4 - 3)^1 + (3 - 6)^1 + (6 - 8)^1 + (8 - 1)^1 = 2$。 **样例输入/输出 #2 的解释** 对于第一个场景，循环 $(1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (1, 2) \rightarrow (1, 1)$ 的惩罚值为 $(1 - 2)^5 + (2 - 0)^5 + (0 - 9)^5 + (9 - 1)^5 = -26250$。你可以不断重复这个循环，使得你的总惩罚值任意小。类似地，对于第二个场景，你可以先移动到 $(1, 1)$，然后重复相同的循环。 翻译由 DeepSeek V3.2 完成