深さ優先探索に続き、幅優先探索を勉強している。今回も「頻出典型アルゴリズムの演習問題としてよさげなやつ」に載っている問題から、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 してみたら、あっさり通った。案ずるより産むが易しだ。この辺の、計算量の感覚がまだつかめない。