P15156 [SWERC 2024] Recovering the Tablet

很久以前，在我们的现代文明兴起之前，在你们任何人出生之前，是公元前 1966 年（SWERC 前 3961 年）。在这段黑暗时期，既没有流媒体服务，也没有编程竞赛。因此，为了自娱自乐，人类在泥板上玩一些简单的游戏。 这一年，一个神秘的游戏被创造出来：Kakurus。我们对 Kakurus 几乎一无所知（互联网档案馆尚未创建），除了你在一个文物上发现的几条规则： 1. 游戏在一个 $M \times N$ 的网格上进行； 2. 每个单元格要么是黑色，要么是白色； 3. 白色单元格最初是空的，但你需要给每个白色单元格填入一个 $1$ 到 $9$（含）之间的整数； 4. **水平约束**：一个黑色单元格可以包含一个整数，该整数等于其右侧连续白色单元格（直到第一个黑色单元格或网格边界）中数字的和； 5. **垂直约束**：一个黑色单元格可以包含一个整数，该整数等于其下方连续白色单元格（直到第一个黑色单元格或网格边界）中数字的和。 注意，最后两条规则彼此独立：一个黑色单元格内部可以有 $0$、$1$ 或 $2$ 个整数。还要注意，对数字的重复没有约束。最后，为了使这个问题有趣，每个白色单元格恰好被一个垂直约束和一个水平约束覆盖。 在你的文物底部有一个 Kakurus 网格。它已经被填充，但不一定是正确的解——可能是由于这件古老文物的年代久远而导致的劣化。你能找到一个尽可能接近这个提议的解的有效解吗？ 如果你在一个白色单元格中填写的数字是 $X$，而该单元格在提议的解中的值是 $T$，那么接近分数为 $|X - T|$。网格的最终接近分数是所有单元格接近分数的总和。你的目标是找出可以实现的最小接近分数。

输入的第一行包含三个整数 $M$、$N$ 和 $S$，分别表示网格的行数、列数和求和约束的数量。 接下来是 $M$ 行。这些行的第 $i$ 行仅包含从 $0$ 到 $9$ 的数字。第 $j$ 个字符等于 $0$ 当且仅当位于第 $i$ 行第 $j$ 列（$1 \leq i \leq M$，$1 \leq j \leq N$）的单元格是黑色的，否则等于该单元格（因此是白色的）在提议的解中的值。 然后是 $S$ 行。每行的格式为 $c\ i\ j\ s$，其中 $c$ 等于 $H$ 或 $V$，$1 \leq i \leq M$，$1 \leq j \leq N$，$s$ 是 $1$ 到 $135$（含）之间的整数。在你的解中，位于第 $i$ 行第 $j$ 列的单元格右侧（当 $c = H$ 时）或下方（当 $c = V$ 时）的连续白色单元格的和必须等于 $s$。 保证每个白色单元格恰好被一个垂直约束和一个水平约束覆盖。

如果网格无解，你必须输出 IMPOSSIBLE。否则，你的输出应包含可以实现的最小接近分数。

#### 数据范围 - $1 \leq M \leq 16$ - $1 \leq N \leq 16$ - $0 \leq S \leq 2 \times M \times N$ 翻译由 DeepSeek 完成