[WC2008] 游览计划

题目描述

从未来过绍兴的小D有幸参加了Winter Camp 2008,他被这座历史名城的秀丽风景所吸引,强烈要求游览绍兴及其周边的所有景点。 主办者将绍兴划分为N行M列(N×M)个分块,如下图(8×8): ![](https://cdn.luogu.com.cn/upload/pic/15472.png) 景点含于方块内,且一个方块至多有一个景点。无景点的方块视为路。 为了保证安全与便利,主办方依据路况和治安状况,在非景点的一些方块内安排不同数量的志愿者;在景点内聘请导游(导游不是志愿者)。在选择旅游方案时,保证任意两个景点之间,存在一条路径,在这条路径所经过的每一个方块都有志愿者或者该方块为景点。既能满足选手们游览的需要,又能够让志愿者的总数最少。 例如,在上面的例子中,在每个没有景点的方块中填入一个数字,表示控制该方块最少需要的志愿者数目: ![](https://cdn.luogu.com.cn/upload/pic/15473.png) 图中用深色标出的方块区域就是一种可行的志愿者安排方案,一共需要20名志愿者。由图可见,两个相邻的景点是直接(有景点内的路)连通的(如沈园和八字桥)。 现在,希望你能够帮助主办方找到一种最好的安排方案。

输入输出格式

输入格式


第一行有两个整数,N和M,描述方块的数目。 接下来N行,每行有M个非负整数,如果该整数为0,则该方块为一个景点; 否则表示控制该方块至少需要的志愿者数目。相邻的整数用(若干个)空格隔开, 行首行末也可能有多余的空格。

输出格式


由N+1行组成。第一行为一个整数,表示你所给出的方案中安排的志愿者总数目。 接下来N行,每行M个字符,描述方案中相应方块的情况: '_'(下划线)表示该方块没有安排志愿者; 'o'(小写英文字母o)表示该方块安排了志愿者; 'x'(小写英文字母x)表示该方块是一个景点; 注:请注意输出格式要求,如果缺少某一行或者某一行的字符数目和要求不一致(任何一行中,多余的空格都不允许出现),都可能导致该测试点不得分。

输入输出样例

输入样例 #1

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

输出样例 #1

6
xoox
___o
___o
xoox

说明

所有的 10 组数据中 N, M ,以及景点数 K 的范围规定如下 ![](https://cdn.luogu.com.cn/upload/pic/15474.png) 输入文件中的所有整数均不小于 0 且不超过 2^16 感谢 @panda_2134 提供Special Judge @yzy1 提供了两组hack数据