Time-4 - DekoBoko Mountain

2 secs 1024 MB
matcharate12's icon matcharate12

追記

  • 15:06 入力例3の制約違反を修正しました。

AC報酬: 1010 ラテコイン

Story

matcharate君は凸凹山に行きました。この山は特殊な山で、いつ行っても山の凸凹さが変わるといった特徴を持っています。
実はこの山の調査員の募集があり、matcharate君はそれに参加することにしたのです。

調査内容は、「とりあえず行けるところまで調査できるところまで山の地面の状態を調べる」といったものでした。だいぶ適当な調査ですが、実は山の真の姿を知るための大きな手掛かりになったりするのです。

さすがのmatcharate君でも、スーパーマンでもあるまいし山全体の地面の状態を調べることはできません。
しかしmatcharate君はより多くの報酬をもらおうと、行ける範囲を最大化したいと思っています。

問題

HH マス、横 WW マスのマス目状の盤面 AA があります。
ここで上から ii 行目左から jj 列目のマスを (i,j)(i,j) で表すとするとき、そのマス (i,j)(i,j)高さAi,jA_{i,j} で表されます。

matcharate君はこの盤面のいずれか 11 つのマスを選び、そのマスに数値関係なく降り立ちます。
そしてそのマスから上下左右に移動することを繰り返し行います。

しかしmatcharate君は体力がないので、移動先のマスの高さと、移動元のマスの高さの差の絶対値が KK 以下でないと移動することはできません。

-Mission-
matcharate君を適切に配置した後、条件を満たす移動方法のうち、移動可能なマスの個数の最大値はいくつか。報告せよ。

入力

入力は以下の形式で与えられる。

HHWWKK
A1,1A_{1,1}A1,2A_{1,2}\dotsA1,WA_{1,W}
A2,1A_{2,1}A2,2A_{2,2}\dotsA2,WA_{2,W}
\vdots
AH,1A_{H,1}AH,2A_{H,2}\dotsAH,WA_{H,W}

制約

  • 2H,W302\le H,W\le 30
  • 0K1030\le K\le 10^3
  • 0Ai,j1030\le A_{i,j}\le 10^3

出力

答えを出力せよ。

入出力例

入力例1
3 5 1
1 6 2 2 9
6 4 2 7 5
1 9 4 7 8
出力例1
3

例えばmatcharate君をマス (3,5)(3,5) に配置すると、移動可能なマスは (3,5),(3,4),(2,4)(3,5),(3,4),(2,4)33 つ、すなわち移動できるマスはスタート含め 33 つ存在します。 どのマスをに配置しようと 44 つ以上移動することはできません。

入力例2
2 2 0
1 2
3 4
出力例2
1

どのマスに配置したとしても条件を満たすような移動先のマスは存在せず、最初に選んだマスのみです。

入力例3
3 3 1000
1 1000 1
1000 1 1000
1 1000 1
出力例3
9

matcharate君がスーパーマンである可能性もあります。どのマスからスタートしても条件を満たすのはすべてのマスです。

入力例4
6 7 12
84 104 97 110 107 36 36
121 111 117 36 36 36 36
102 111 114 36 36 36 36
99 111 109 105 110 103 36
116 111 36 36 36 36 36
77 83 65 66 67 33 33
出力例4
18

Submit


Go (1.21)