/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
注意
この問題に対する言及は、2019年12月29日 05:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。
試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。
問題文
縦 H マス、横 W マスの合計 H \times W 個の正方形のマスに区切られた区画がある。左下隅、右下隅、右上隅の 3 マスを除いてこれらのマスはすべて未整備で、上から i 行目、左から j 列目 (1 \leqq i \leqq H, 1 \leqq j \leqq W) のマスを整備するのに必要な費用は A_{i,j} 円である。
区画の左下隅のマスに物体が置かれている。あなたは、これをまず右下隅のマスまで移動させ、次に右上隅のマスまで移動させようとしている。
物体の移動は、物体が現在占有するマスから上下左右に隣接するマスに動かすことを繰り返して行う。このとき、物体が通るマスはすべて整備されている必要がある。一度整備を行ったマスの上は何度でも物体を通すことができる。
このとき、マスの整備に必要な最小の合計費用を求めよ。
制約
- 2 \leqq H, W \leqq 50
- 0 \leqq A_{i,j} \leqq 100,000
- A_{H,1} = A_{H,W} = A_{1,W} = 0
- 入力中の値はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
H W
A_{1,1} A_{1,2} \ldots A_{1,W}
A_{2,1} A_{2,2} \ldots A_{2,W}
:
A_{H,1} A_{H,2} \ldots A_{H,W}
出力
必要な最小の合計費用を表す整数を出力せよ。
入力例 1
5 6 9 9 9 9 1 0 9 9 9 9 1 9 9 9 9 1 1 1 9 1 1 1 9 1 0 1 9 9 9 0
出力例 1
10
整備費用が 1 円のマスをすべて整備するのが最適である。
入力例 2
10 10 1 2 265 1544 0 1548 4334 9846 58 0 21 0 50 44 2 388 5 0 0 4 170 0 2 1 54 1379 50 3 41 0 310 0 1 0 2163 0 226 26 3 12 151 33 0 9 0 0 0 36 365 2286 0 3 12 3 9 317 645 100 21 4 52 1 569 0 144 0 6 202 25 0 8869 19 2058 1948 1252 1002 7 1750 0 5 0 3 8 29 2 4403 0 0 0 5 0 17 93 9367 159 6 1 216 0 0
出力例 2
246
Warning
Do not make any mention of this problem until December 29, 2019, 05:00 a.m. JST. In case of violation, compensation may be demanded.
After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).
Problem Statement
There is a rectangular piece of land divided into a grid of H \times W squares with H horizontal rows and W vertical columns. Except for the three squares at the bottom-left, bottom-right, and top-right corners of the grid, all the squares are unpaved. Paving the square at the i-th row from the top and the j-th column from the left (1 \leq i \leq H, 1 \leq j \leq W) costs A_{i,j} yen (the currency of Japan).
We have an object in the square at the bottom-left corner of the grid. You want to carry it to the square at the bottom-right corner, then to the square at the top-right corner.
To carry the object, you need to repeat moving it from a square to another square that is horizontally or vertically adjacent to the square currently occupied. Here, all the squares that the object goes through must be paved. Once a square is paved, the object may go through that square any number of times.
Find the minimum amount of money needed to pave squares for your objective.
Constraints
- 2 \leq H, W \leq 50
- 0 \leq A_{i,j} \leq 100000
- A_{H,1} = A_{H,W} = A_{1,W} = 0
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
H W
A_{1,1} A_{1,2} \ldots A_{1,W}
A_{2,1} A_{2,2} \ldots A_{2,W}
:
A_{H,1} A_{H,2} \ldots A_{H,W}
Output
Print the integer representing the minimum amount of money.
Sample Input 1
5 6 9 9 9 9 1 0 9 9 9 9 1 9 9 9 9 1 1 1 9 1 1 1 9 1 0 1 9 9 9 0
Sample Output 1
10
It is optimal to pave all the squares costing 1 yen to pave.
Sample Input 2
10 10 1 2 265 1544 0 1548 4334 9846 58 0 21 0 50 44 2 388 5 0 0 4 170 0 2 1 54 1379 50 3 41 0 310 0 1 0 2163 0 226 26 3 12 151 33 0 9 0 0 0 36 365 2286 0 3 12 3 9 317 645 100 21 4 52 1 569 0 144 0 6 202 25 0 8869 19 2058 1948 1252 1002 7 1750 0 5 0 3 8 29 2 4403 0 0 0 5 0 17 93 9367 159 6 1 216 0 0
Sample Output 2
246