seuOJ511 - Nanami and the House Protecting Problem

• 题目类型：传统
• 输入文件：标准输入流
• 输出文件：标准输出流
• 时间限制：1000 ms
• 空间限制：1024 MiB
• 题目标签：夏季, 2024

题目描述

长大后，Nanami 开始玩电脑游戏。

Nanami 在玩 Minecraft，Minecraft 的地图可以看做一个 $n\times m$ 的网格。从这个网格外会源源不断地出现怪物，所以Nanami 需要建立一个有障碍物构成的墙来保护她的房子。怪物在移动时，可以移动到与当前网格有公共边的任意空的网格。

而网格内包含以下三种类型：'.' 代表空网格，'#' 代表有障碍物的网格，'H' 代表 Nanami 的家。Nanami 可以在任意的没有障碍物或者房子的格点放置一个新的障碍物。

同时，Minecraft 还有一个设定，那就是在不同的格点放置障碍物的代价是不同的。换句话来说，还有一个二维矩阵 $a$，在格点 $(i,j)$ 放置障碍物的价格为 $a_{i,j}$。

Nanami 想问你，如果她想要保护她的所有房子，她需要付出的最小的价格是多少呢。

输入格式

第一行，一个整数 $t(1\le t \le 333)$，代表数据组数。

对于每组数据：

第一行，两个整数 $n,m(3\le n,m \le 1000)$，代表 Minecraft 地图的大小。

接下来的连续的 $n$ 行，每行一个由 '.'，'#'或 'H' 构成的字符串，代表 Minecraft 的地图。

接下来连续的 $n$ 行，每行 $m$ 个整数 $a_{i,j},\dots,a_{i,m}(0\le a_{i,j}\le 10^5)$，代表在格点 $(i,j)$ 放置障碍物的价格 $a_{i,j}$。

保证房子（即 'H'）不会出现在地图边界上且地图上至少有一个 'H'。

保证矩阵 $a$ 所有对应位置不为 '.' 的位置的价格为 $0$，为 '.' 对应位置的价格大于 $0$。

保证同一测试点内 $n\times m$ 的和不超过 $3000$。

输出格式

对于每组数据，先输出一行整数 $c$，代表 Nanami 需要付出的最小价格。接下来输出 $n$ 行长度为 $m$ 的字符串，每个字符为 '.'，'#'或 'H'，代表 Nanami 的放置障碍物的方案，注意 Nanami 只能在空格放置障碍物，不能移动现有的障碍物或者她的房子。

任何符合题目要求的方案都是正确的。

样例

输入样例

5
3 3
.#.
#H.
.#.
1 0 1
0 0 2
1 0 1
3 3
###
#H#
###
0 0 0
0 0 0
0 0 0
5 6
#...#.
...H..
##..##
...#.#
###...
0 1 2 2 0 9
1 1 9 0 3 1
0 0 1 1 0 0
9 9 9 0 9 0
0 0 0 8 8 8
4 4
.##.
.H.#
..H.
.#..
23 0 0 75
13 0 42 0
1 25 0 1
17 0 13 96
6 5
.....
.H...
.....
.....
.H...
...#.
2 1 2 1 1
2 0 3 2 1
2 2 1 2 1
3 2 3 1 1
1 0 2 2 2
2 2 1 0 1

输出样例

2
.#.
#H#
.#.
0
###
#H#
###
7
#.###.
.#.H.#
###.##
...#.#
###...
28
.##.
#H.#
#.H#
.##.
15
.#...
#H#..
.#...
.#...
#H#..
.#.#.