CF152E Garden

Vasya 有一个非常美丽的乡村花园，这个花园可以表示为一个 $n \times m$ 的矩形地块，被分成 $n \cdot m$ 个小方格。在某个美丽的日子里，Vasya 突然想起，他需要在 $k$ 个重要方格（这些方格里有建筑物）之间铺设道路。为了铺设道路，他可以用混凝土覆盖花园中的部分方格。 我们知道每个花园方格中有 $a_{i,j}$ 朵花，表示在坐标为 $(i, j)$ 的方格上生长着多少朵花。当某个方格被混凝土覆盖后，这个方格上的所有花都会死亡。 Vasya 想要按如下条件用混凝土覆盖一些方格： - 所有 $k$ 个重要方格必须被混凝土覆盖； - 任意两个重要方格之间必须可以通过仅走被混凝土覆盖的相邻方格（即有公共边的方格）连通； - 死亡的花的总数应尽可能少。 由于 Vasya 的花园比较大，他希望你帮他完成这个任务。

第一行输入三个整数 $n$，$m$ 和 $k$（$1 \leq n, m \leq 100$，$n \cdot m \leq 200$，$1 \leq k \leq \min(n \cdot m, 7)$），分别表示花园的大小以及重要方格的数目。接下来的 $n$ 行，每行 $m$ 个数字 $a_{i,j}$（$1 \leq a_{i,j} \leq 1000$），表示每个方格里的花的数量。之后再输入 $k$ 行，每行两个整数 $x$ 和 $y$（$1 \leq x \leq n$，$1 \leq y \leq m$），表示一个重要方格的坐标。保证所有 $k$ 个重要方格的位置各不相同。

第一行输出一个整数，表示在修路过程中死亡的最少花的数目。接下来输出 $n$ 行，每行 $m$ 个字符，表示花园的方案。用大写 'X' 表示被混凝土覆盖的方格，用点 '.' 表示没有被覆盖的方格。如果有多种方案，输出其中任意一种即可。

由 ChatGPT 5 翻译