AOJ 0243 (Filling Game : 塗りつぶしゲーム)
【問題】
https://onlinejudge.u-aizu.ac.jp/problems/0243
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0243
【解説】
色は3通りあり、現在の左上の色の状態と同じ色のボタンを押す操作は無意味なため、現在の色以外のボタンを押したときの2通りについて、押した後の盤面の状態と操作回数をノードとしてキューに格納する幅優先探索を行う。
2通りのボタンを押した場合のどちらでも、色を変えるべきマス(=現在の左上の盤面から連続している同色のマス)は同様なため、キューから取り出した後、深さ優先探索を行い、色を変えるべきマスを配列に保持しておくことで、処理時間を短縮することができる。
【コード】