题目链接

简化题意

已知一个 $n\times m$ 的矩阵，控制 $(i,j)$ 需要 $a_{i,j}$ 的代价。

有 $k$ 个满足 $a_{i,j}=0$ 的点，这些点为关键节点。

求将所有关键节点联通所需要的最小代价。

此处联通为四联通。

输入格式

第一行有两个整数，N和M，描述方块的数目。

接下来N行，每行有M个非负整数，如果该整数为0，则该方块为一个景点；

否则表示控制该方块至少需要的志愿者数目。相邻的整数用（若干个）空格隔开，

行首行末也可能有多余的空格。

输出格式

由N+1行组成。第一行为一个整数，表示你所给出的方案中安排的志愿者总数目。

接下来N行，每行M个字符，描述方案中相应方块的情况：

'_'（下划线）表示该方块没有安排志愿者；

'o'（小写英文字母o）表示该方块安排了志愿者；

'x'（小写英文字母x）表示该方块是一个景点；

注：请注意输出格式要求，如果缺少某一行或者某一行的字符数目和要求不一致（任何一行中，多余的空格都不允许出现），都可能导致该测试点不得分。

4 4
0 1 1 0
2 5 5 1
1 5 5 1
0 1 1 0

6
xoox
___o
___o
xoox

提示

所有的 10 组数据中 N, M ，以及景点数 K 的范围规定如下

输入文件中的所有整数均不小于 0 且不超过 2^16

感谢@panda_2134 提供Special Judge