Time-4 - DekoBoko Mountain

2 secs 1024 MB

追記

AC報酬: $10$ ラテコイン

⛰

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

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

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

縦 $H$ マス、横 $W$ マスのマス目状の盤面 $A$ があります。
ここで上から $i$ 行目左から $j$ 列目のマスを $(i,j)$ で表すとするとき、そのマス $(i,j)$ の高さは $A_{i,j}$ で表されます。

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

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

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

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

$H$ $W$ $K$
$A_{1,1}$ $A_{1,2}$ $\dots$ $A_{1,W}$
$A_{2,1}$ $A_{2,2}$ $\dots$ $A_{2,W}$
$\vdots$
$A_{H,1}$ $A_{H,2}$ $\dots$ $A_{H,W}$

答えを出力せよ。

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

2 2 0
1 2
3 4

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

3 3 1000
1 1000 1
1000 1 1000
1 1000 1

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

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

登録なしで提出できます。

Go (1.21)