D - SaitaMaze
Milk
2
s
1024
MB
100
点
問題文
縦 $H$ マス、横 $W$ マスのグリッド状の埼玉大学があります。
上から $i$ 行目・左から $j$ 列目のマスを $(i,j)$ とします。マス $(i,j)$ の高さは $h_{i,j}$ です。
Maximum 君は埼玉大学に迷い込んでしまいました。
埼玉大学から脱出するには、現在地 $(0, 0)$ から出口の $(H-1, W-1)$ に移動する必要があります。
しかし、埼玉大学の地形は非常に険しく、上下左右に隣接する同じ高さのマスに限り直接移動することができます。
Maximum 君は魔力を 1 消費することで、任意のマスの高さを変更する特殊能力を持っています。
特殊能力は現在いるマスとは関係なく、任意のマスに対して発動することができます。
$(0, 0)$ から $(H-1, W-1)$ に到達する際に消費する魔力の最小値を求めてください。
制約
- $1 \leq H,W \leq 200$
- $1 \leq h_{i,j} \leq 10^9$
- 任意の整数 $x$ について、 $h_{i,j}=x$ なる $(i,j)$ は最大で 20 個まで存在する。
部分点
この問題はいくつかの小課題に分けられ、その小課題の全てのテストケースに正解した場合に、「この小課題に正解した」とみなされます。
提出したソースコードの得点は、正解した小課題の点数の合計となります。
- （1 点） $h_{i,j}$ は相異なる。
- （99 点） 追加の制約はない。
入力
入力は以下の形式で標準入力から与えられる。
$H$ $W$
$h_{1,1}$ $h_{1,2}$ ... $h_{1,W}$
$h_{2,1}$ $h_{2,2}$ ... $h_{2,W}$
$:$
$h_{H,1}$ $h_{H,2}$ ... $h_{H,W}$
$h_{1,1}$ $h_{1,2}$ ... $h_{1,W}$
$h_{2,1}$ $h_{2,2}$ ... $h_{2,W}$
$:$
$h_{H,1}$ $h_{H,2}$ ... $h_{H,W}$
出力
$(0, 0)$ から $(H-1, W-1)$ に到達する際に消費する魔力の最小値を出力せよ。
入力例 1
4 4
10000 10001 10010 10011
10100 10101 10110 10111
11000 11001 11010 11011
11100 11101 11110 11111
出力例 1
6
最適にマスの高さを変更すると、6 回の特殊能力を使うことで $(0, 0)$ から $(H-1, W-1)$ に到達できます。
なお、この入力例は小課題 1, 2 の制約を満たします。
入力例 2
5 5
1 4 5 5 5
1 4 2 2 3
1 4 2 6 3
1 1 2 6 3
4 4 5 5 3
出力例 2
2
特殊能力は移動途中に自分のいるマスにも適用できます。
なお、この入力例は小課題 2 の制約を満たします。
入力例 3
10 10
3 1 4 1 5 9 2 6 5 3
5 8 9 7 9 3 2 3 8 4
6 2 6 4 3 3 8 3 2 7
9 5 7 2 8 8 4 1 9 7
1 6 9 3 9 9 3 7 5 1
2 5 8 2 1 9 7 9 4 4
5 9 2 3 7 7 8 1 6 4
4 6 2 8 6 2 5 8 9 9
8 6 2 8 9 3 4 8 2 5
3 4 2 1 1 7 2 6 7 9
出力例 3
10
この入力例は小課題 2 の制約を満たします。