AGC 043 A - Range Flip Find Route
ルートの網羅をどう実装してよいか定まらずめちゃくちゃ手こずった
初手の方針
マス目の . -> # への変化をカウントしようとした。
例えば S[i-1][j] -> S[i][j] で . -> # と変化する場合カウントは count[i][j] = count[i-1][j]+1 といった感じ。
S[i][j]へ進むパターンがS[i-1][j]とS[i][j-1]の2パターンありえるので、探索は各マス目の訪問済みフラグを持たずに幅優先探索を行おうとした。（訪問フラグを持つと一度訪問したマス目に改めて訪問することができないため）
通常の幅優先探索の場合だと頂点がW*Hで辺が2*W*H（ちょっと頂点と辺の数え上げに自信がない）となるので、訪問済みフラグを外しても100×100くらいであれば間に合うと思いこの方法で進めたがTLE連発でACせず。このあたりの計算量が感覚的にわかっておらずなんとなく間に合う気がして訪問済みフラグなしで幅優先探索を行おうとしてしまった。
Submission #11866572 - AtCoder Grand Contest 043
正答
幅優先探索しなくてもS[i-1][j]とS[i][j-1]それぞれのcountを記憶しておくだけで良く、. -> #の変化を加味してS[i][j]はmin(S[i-1][j],S[i][j-1])ormin(S[i-1][j]+1,S[i][j-1])ormin(S[i-1][j],S[i][j-1]+1)のいずれかとなる。
S[i][j]->#, S[i-1][j]->#,S[i][j-1]-># count[i][j]=min(count[i-1][j]+1,count[i][j-1]+1) S[i][j]->#, S[i-1][j]->.,S[i][j-1]-># count[i][j]=min(count[i-1][j]+1,count[i][j-1]) S[i][j]->#, S[i-1][j]->#,S[i][j-1]->. count[i][j]=min(count[i-1][j],count[i][j-1]+1) それ以外 count[i][j]=min(count[i-1][j],count[i][j-1])
計算量はW*Hでありデータ構造はマス目そのものを表す2次元vectorと各マス目の操作回数の最小値を表す2次元vectorを用意する。
Submission #11867983 - AtCoder Grand Contest 043
振り返り
- 訪問済みフラグがないと幅優先探索は成り立たない
- ルート網羅系の問題で愚直に全ルート列挙は間に合わないのでDPなどを検討する
- W*Hのマス目が題材となっている問題ではテストデータはW≠Hで用意するとバグが検知しやすい
