分数: 6 点
问题陈述
有一个网格 H 水平行和 W 垂直列。 广场位于 i从顶部开始的第行和 j从左边算起的第列称为 (i, j)。 每个方块的状态要么是“空方块”,要么是“有墙的方块”。 最初,每个方格都是空方格。
A女士想乘车从 (1, 1) to (H, W)。 当A女士在 (i, j),她可能会搬到其中之一 (i+1,j),(i,j+1),(i-1,j),和 (i,j-1)。 她无法走出网格或移动到有墙的广场。
B女士决定选择一些方格来建造围墙,这样A女士就无法到达 (H, W) 无论她如何移动。
B女士花费了 c_{i, j} 日元(日本的货币)筑墙 (i, j)。 她无法在上面建造一堵墙 (1, 1) or (H, W).
B女士要满足条件至少需要支付多少费用? 另外,打印建造墙壁的方式,以达到最小的成本。
约束
- 2 \leq H, W \leq 20
- 1 \leq c_{i,j} \leq 10^9 (1 \leq i \leq H, 1 \leq j \leq W, (i,j) \neq (1,1), (i,j) \neq (H,W))
- c_{1,1} = c_{H,W} = 0
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
H W
c_{1,1} c_{1,2} \dots c_{1,W}
c_{2,1} c_{2,2} \dots c_{2,W}
\vdots
c_{H,1} c_{H,2} \dots c_{H,W}
输出
打印 H+1 行。
的 1-st 行应包含 B 女士应支付的最低费用。
的 2-nd 及后续行应采用以下格式。 在这里, G_{i,j} = . 意味着她不会在上面筑墙 (i, j); G_{i,j}= # 意味着她将在上面建造一堵墙 (i,j).
G_{1,1}G_{1,2}\dotsG_{1,W}
G_{2,1}G_{2,2}\dotsG_{2,W}
\vdots
G_{H,1}G_{H,2}\dotsG_{H,W}
如果有多种方法可以实现最低成本,请打印其中任何一种。
样本输入 1
2 3 0 6 4 2 3 0
示例输出 1
7 ..# .#.
如果B女士付款 7 日元建墙 (1, 3) 和 (2, 2),A女士将无法联系到 (2, 3).
由于不可能以更少的成本满足条件,所以这就是答案。
示例输入 2
4 3 0 9 2 9 3 9 2 3 9 3 9 0
示例输出 2
7 ..# .#. #.. ...
示例输入 3
2 2 0 1000000000 1000000000 0
示例输出 3
2000000000 .# #.