ABC 401-500/ABC427E - Wind Cleaning - 競技プログラミング用 知識集積所

---

問題

ABC427E

必要知識

B以下レベルの内容は省略

• 幅優先探索※

考え方

最小手数を求めるので、各状態を頂点にとるグラフの幅優先探索※を考える。
問題は、各状態とは何を指すのか、である。

まず、各ゴミがデフォルトの位置からどれだけ動いたところにいるか（あるいは、高橋君がもともとのどの位置相当にいるか）が必要。
これは、この変数が変化することが1手になるのだから、欠かすことは絶対にできない。

そして、同じ位置にいてもゴミがどこまで消えているかの情報も必要。
例えば入力例1で「上、下」と移動した場合、ゴミの位置は基本的には元々の位置に戻っているが、最上段のものは消滅しているため、状況が変わっているからである。
つまり、各辺の方向から何列が消滅済か（あるいは、最大でその方向に何マス分まで動かしたことがあるか）の情報も必要。

以上から、6つの変数を持つ状態を定義することになる。
各状態から、高橋君が汚れないような移動方向（最大4つ）に動かした状態へ辺が張ってあるとおもって6次元の幅優先探索※をすればよい。

さて、問題は計算量が間に合うか。
まず、ゴミの移動位置だが、上下それぞれHまで動かせば確実にゴールになるので2H通り。
そして何行が消滅済かは、上からと下からが足してHになったらゴールしている。
さらにゴミが全部消滅済かの確認の全探索※で、行ごと消滅済でないところを走らせるループがある。
よって、Hに関連する部分はO(H^4)となる。
ただし、「上から何行消滅済か」「下から何行消滅済か」「全探索で選ぶ行」は実質0以上H未満の異なる整数を3つ選ぶようなものだし、ゴミの移動位置と消滅行の間にも制約があるので、その係数は1/12となる。
Wに関する部分も同様にO(W^4)で、その係数は1/12。
ということは、最大入力でも、12^8/12^2で約300万通りのループで済み、間に合う。

解答例

解答例

注意点

別解

二次元累積和※を使う

ゴミの個数の判断、毎回全探索※をしなくても、二次元累積和※を使うことでO(1)で済ませることができる。
ただし、H,W<=12という制約だと、そこまでの高速化は必要ない。