言いたいこと
・グリッドの同じ座標を何度も見る場合、O(4^HW)がかかってTLEする(下の問題など)
・グリッドの各座標を最大で一回しか見ない場合、O(4HW)でACできる(水たまりの連結成分の個数を求める問題など)
バックトラックの計算量
https://atcoder.jp/contests/abc348/tasks/abc348_d
この問題の解説放送でバックトラックが指数時間かかるということを知りました。グリッドのサイズがHWのとき、バックトラックをすると計算量は各座標で4方向見るので4HWだと思っていましたが、実際は4^(HW)でした。ただし例外として、水たまりの塊の数を求めるなどの連結成分を求める問題などは4HWになります。下の説明を見ていただければわかると思います。
わかりやすいイメージとしては、4HWの場合は「グリッドの各座標を一回ずつ訪れて4方向見る」ということになります。しかし4^(H*W)の場合は、「dfsをしていて、何度も同じ座標を訪れているかもしれないが毎回4方向見る」という感じになります。
つまり何度も同じ座標を訪れていて毎回4方向見るというのが問題になっています。
ちなみに4^(HW)でなぜHWなのかという部分は、「ある地点からdfsをスタートして、そこから四方向の一つに進んで、さらに進んでと繰り返した結果、綺麗にグリッドを全て見ることができた。そしてdfsをreturnして戻ってきて、その戻ってきた毎回の場所からまだ見ていない4方向を選んで進んで、その進み方でも毎回綺麗にグリッドを全て見ることができた」みたいなのをイメージすればなんとなくわかると思います。実際にH*Wというわけではなく目安としてのサイズとして覚えてもらえればいいと思います(O(2^30)でTLEなのでそれを超えているとわかっているだけでもいいと思います)
図にしてみるとこんな感じです。言いたいのは「無数とまではいかないが、とてつもない計算量がかかるほどの通りがある」ということです、数え上げお姉さんと似た香りがします。ただこれはあくまで上に貼った問題のリンクのような一度通った座標を何度も通る可能性がある問題の場合で、最初に書いた通り水たまりの塊の数を求めるような連結成分を求める場合は4HWになります。
おわりに
今まで当然のようにバックトラックを4HWだと思っていて、上の問題を本番で解いてTLEして痛い目に遭いました。解説放送でバックトラックについてコメントしてくれた方とsnukeさんに感謝します。