← 返回题目列表

AtCoder · past202206_n

N. 建筑平面图

中文机器翻译题面 查看原题

分数: 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
.#
#.