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.