← 返回题目列表

Codeforces · 152/E

E. 花园

中文机器翻译题面 查看原题

Vasya 有一个非常美丽的乡村花园,可以表示为一个 n × m 的矩形田地,分为 n·m 个正方形。美好的一天,瓦夏想起他需要在包含建筑物的 k 个重要广场之间铺设道路。为了铺路,他可以用混凝土覆盖花园的一些广场。

对于每个花园方块,我们知道数字 aij 代表坐标为 (i, j) 的方块中生长的花朵数量。当一个广场被混凝土覆盖时,广场上生长的所有花朵都会枯死。

Vasya 想要用混凝土覆盖一些广场,以便满足以下条件:

- 所有 k 个重要的方块都必须用混凝土覆盖
- 从每个重要的方格都应该有一条通往任何其他重要方格的路。考虑到相邻的正方形是具有公共边的正方形,所以应该用混凝土覆盖的正方形铺路
- 死亡植物总数应最少

由于 Vasya 有一个相当大的花园,他请求你帮助他。

输入

第一输入行包含三个整数 n、m 和 k (1 ≤ n, m ≤ 100, n·m ≤ 200, 1 ≤ k ≤ min(n·m, 7)) — 花园的大小和重要方块的数量。接下来的 n 行中的每一行都包含 m 个数字 aij (1 ≤ aij ≤ 1000) — 方块中花朵的数量。接下来的 k 行包含重要方块的坐标,写为“x y”(不带引号)(1 ≤ x ≤ n,1 ≤ y ≤ m)。写在一行上的数字用空格分隔。保证所有k个重要的方格都有不同的坐标。

输出

在第一行中打印单个整数——道路施工期间死亡的植物的最小数量。然后打印 n 行,每行包含 m 个字符——花园的平面图。在本方案中,用字符“X”(大写拉丁字母X)来表示混凝土覆盖的正方形,并使用字符“.”。 (点)表示未覆盖混凝土的正方形。如果有多个解决方案,请打印其中任何一个。

示例

输入 #1

3 3 2
1 2 3
1 2 3
1 2 3
1 2
3 3

输出 #1

9
.X.
.X.
.XX

输入 #2

4 5 4
1 4 5 1 2
2 2 2 2 7
2 4 1 4 5
3 2 1 7 1
1 1
1 5
4 1
4 4

输出 #2

26
X..XX
XXXX.
X.X..
X.XX.