/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 6 点
問題文
縦横 H \times W マスのグリッドがあります。上から i 行目、左から j 列目のマスを (i,j) と表します。 各マスの状態は「何もないマス」か「壁があるマス」のいずれかです。はじめ、全てのマスは何もないマスです。
A さんは (1, 1) を出発してグリッド上を移動して (H, W) へ行こうとしています。A さんは (i,j) にいるときに (i+1,j),(i,j+1),(i-1,j),(i,j-1) のいずれかに移動することができます。ただし、グリッドの外に出るような移動や、壁があるマスへの移動を行うことはできません。
B さんは、A さんが移動を開始する前にいくつかのマスを選んで壁を建てることで、A さんがどのように移動しても (H, W) へ行くことができないようにすることにしました。
B さんが (i, j) に壁を建てるには c_{i, j} 円を払う必要があります。また、(1, 1), (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 行目には B さんが支払う最小の金額を出力せよ。
2 行目以降は以下の形式で出力せよ。ただし、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 .# #.
Score : 6 points
Problem Statement
There is a grid with H horizontal rows and W vertical columns. The square at the i-th row from the top and the j-th column from the left is called (i, j). The state of each square is either an "empty square" or a "square with a wall". Initially, every square is an empty square.
Ms. A wants to travel on the grid from (1, 1) to (H, W). When Ms. A is at (i, j), she may move to one of (i+1,j),(i,j+1),(i-1,j), and (i,j-1). She cannot go outside the grid or move to the square with a wall.
Ms. B has decided to choose some of the squares to build walls so that it is impossible for Ms. A to reach (H, W) no matter how she moves.
It costs Ms. B c_{i, j} yen (the currency in Japan) to build a wall on (i, j). She cannot build a wall on (1, 1) or (H, W).
What is the minimum cost Ms. B has to pay so that the condition is satisfied? Also, print the way of building walls to achieve the minimum cost.
Constraints
- 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
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
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}
Output
Print H+1 lines.
The 1-st line should contain the minimum cost that Ms. B should pay.
The 2-nd and subsequent lines should be in the following format. Here, G_{i,j} = . means she will not build a wall on (i, j); G_{i,j}= # means she will build a wall on (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}
If there are multiple ways to achieve the minimum cost, print any of them.
Sample Input 1
2 3 0 6 4 2 3 0
Sample Output 1
7 ..# .#.
If Ms. B pays 7 yen to build walls on (1, 3) and (2, 2), Ms. A will be unable to reach (2, 3).
Since it is impossible to satisfy the condition with less cost, this is the answer.
Sample Input 2
4 3 0 9 2 9 3 9 2 3 9 3 9 0
Sample Output 2
7 ..# .#. #.. ...
Sample Input 3
2 2 0 1000000000 1000000000 0
Sample Output 3
2000000000 .# #.