AOJ 0503 - Cup(JOI2005予選4)

コップ | Aizu Online Judge

提出コード
ハノイの塔の制限をきつくしたような問題です。
基本的には幅優先探索をベースに考えます。
1回の手順で行う操作はA→B、B→A、B→C、C→Bの4通りなので、ある状態に対して、その4通りを行えれば行う、ということを繰り返していけばいいという考えにたどり着きます。終了条件はもちろん「全てのコップがAにあるかCにある」、という状態で、その時までにかかる手数を出力します。
ここで問題の制限を見ると、mの制限が 15000000 以下であるため、単純計算となり、とてもじゃないですが間に合いそうにありません(操作は4通りですが、毎回4通り全てを行うことができるわけではないので、実際はもっと減りますがどちらにしろ間に合いません)。そこでどうにかならないかと考えると、nの制限が15以下ということに目がいきます。
トレイは3種類あり、置き方は一意に決まる(大きいものを上にかぶせることしかできない)ので、状態の数はたかだか通りです。この計算結果は14348907なので、3つのトレイのとある状態が既に探索済みであるかどうかをメモしていれば、多くても14348907通りしか調べないことになるので、時間内に探索が間に合いそうです。
さて、置き方の区別のつけ方ですが、3進数を上手く活用してあげるといいかと思います。
コップの種類(1~15)を桁数、トレイA~Cを0~2に置き換えて桁の数字とします。そして、

の総和を求めてあげると、全ての置き方を異なる数字で記録できます。あとは配列の添え字を対応させて、boolなりを用い、すでに探索済みかどうかメモしてあげれば答えがもとまります(幅優先探索なので、探索済みかどうかさえわかればいいです)。