深さ優先探索に続き、幅優先探索を勉強している。今回も「頻出典型アルゴリズムの演習問題としてよさげなやつ」に載っている問題から、2題解いてみた。
AOJ 0179: Mysterious Worm
それほど悩まずに解けた。無限ループを避ける工夫をしている。
AOJ 0558: Cheese
こちらもそれほど悩まなかった。スタートとゴールを変えてN回探索している。
という感じで、このくらいの問題は解けるようになってきた。残りの問題はまた今度。
AOJ 0121: Seven Puzzle (2015-08-31)
これは難しかった。単純に探索するだけでは TLE (Time Limit Exceeded) してしまう。他の回答を参考に工夫したら、格段に早くなった。発想が大事なのだと改めて感じた。
それだけでなく、右上と左下のカードが入れ替えられるバグがあることに気づかず、WA (Wrong Answer) も出してしまった。簡単な問題が解けたせいで慢心していたのかもしれない。
AOJ 0223: Stray Twins (2015-09-02)
単純な幅優先探索では解けないのではないかと、だいぶ悩んでしまった。結局、特に工夫のないコードを Submit してみたら、あっさり通った。案ずるより産むが易しだ。この辺の、計算量の感覚がまだつかめない。