Garden

题意翻译

## 题目意思： $Vasya$有一个非常漂亮的花园。花园由$n*m$个长着花的土地组成。土地$(i,j)$上的花的数目为$a_{i,j}$。 一天，$Vasya$突然想起他要给他的花园中的$k$个土地建造大厦。同时，他还需要在其他若干个土地上铺上混凝土，使得每个大厦都能与别的大厦连通。（如果从一个大厦$i$出发，只走铺有混凝土的土地，能到达大厦$j$，说明大厦$i$与大厦$j$是连通的。） 当$Vasya$给一个土地建造大厦或铺上混凝土时，这个格子里的所有的花朵都会死去。 $Vasya$十分喜爱花朵，所以他希望死去的花的数目尽可能的少。 ## 输入： 第一行给你3个数$n,m,k$，表示花园的行数，花园的列数，大厦的个数。 接下来$n$行，每行$m$个数$a_{i,j}$，即每个位置花的数。 接下来$k$行，每行两个数$x,y$，表示位置$(x,y)$需要建造大厦。 ## 输出： 第一行输出一个整数：最小的死去的花的数目。 接下来$n$行，每行有$m$个字符，表示方案。对于位置$(i,j)$，如果该位置的土地上的花死去了，则输出‘X’，否则输出‘.’。 ## 数据范围 $$ 1\le n,m\le 100,n*m \le200$$ $$1 \le k \le \min(n*m,7)$$ $$ 1\le a_{i,j} \le 1000 $$ $$ 1\le x \le n,1\le y \le m$$

题目描述

Vasya has a very beautiful country garden that can be represented as an $ n×m $ rectangular field divided into $ n·m $ squares. One beautiful day Vasya remembered that he needs to pave roads between $ k $ important squares that contain buildings. To pave a road, he can cover some squares of his garden with concrete. For each garden square we know number $ a_{i}_{j} $ that represents the number of flowers that grow in the square with coordinates $ (i,j) $ . When a square is covered with concrete, all flowers that grow in the square die. Vasya wants to cover some squares with concrete so that the following conditions were fulfilled: - all $ k $ important squares should necessarily be covered with concrete - from each important square there should be a way to any other important square. The way should go be paved with concrete-covered squares considering that neighboring squares are squares that have a common side - the total number of dead plants should be minimum As Vasya has a rather large garden, he asks you to help him.

输入输出格式

输入格式

The first input line contains three integers $ n $ , $ m $ and $ k $ ( $ 1<=n,m<=100 $ , $ n·m<=200 $ , $ 1<=k<=min(n·m,7 $ )) — the garden's sizes and the number of the important squares. Each of the next $ n $ lines contains $ m $ numbers $ a_{i}_{j} $ ( $ 1<=a_{i}_{j}<=1000 $ ) — the numbers of flowers in the squares. Next $ k $ lines contain coordinates of important squares written as " $ x $ $ y $ " (without quotes) ( $ 1<=x<=n $ , $ 1<=y<=m $ ). The numbers written on one line are separated by spaces. It is guaranteed that all $ k $ important squares have different coordinates.

输出格式

In the first line print the single integer — the minimum number of plants that die during the road construction. Then print $ n $ lines each containing $ m $ characters — the garden's plan. In this plan use character "X" (uppercase Latin letter X) to represent a concrete-covered square and use character "." (dot) for a square that isn't covered with concrete. If there are multiple solutions, print any of them.

输入输出样例

输入样例 #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.