★★☆[解説]動的計画法(DP)で解けます。ナップザック問題をDPで解く仕組みを応用します。★★★☆[解説]この問題の難易度は、本番のタイムリミットによって大きく左右します(★★☆くらいかも)。審判データで試すと、手元のマシンで3分ほどかかってしまいます。試してみると、案の定劇的な変化はなく30秒程度かかります。Deepening)(縦型探索)がベストという結論に至りました。選手の皆さんはどうやって解いたのでしょうか。何かポイントがありそうです(探索空間を縮小できるとか)。この問題を縦型探索で解くには多少勇気がいる気がします。マンハッタン距離を、現在の状態とゴールの状態における各セル上面の色が違うものの個数としました。その他、マンハッタン距離を大きくするポイントがあれば高速化できるでしょう。反復進化のLIMITの増加値を3とすることで、多少高速化できました。幅優先探索まず、深さ優先探索(バックトラック)で、2と2を繋ぐパスを探します(総当り)。パスを探す過程で、例えば以下のような「無駄な」あるいは「ありえない」部分パスを発見したら枝を刈ります。2222ワイヤーが接してしまう場合202222これらの回転20022222これらの回転*000..00*2000..0022222..222これらの回転などなど、、.(ここまで刈ればPOJでも受理されます)2と2を繋ぐパスを発見したときに、3と3を繋ぐ最短パスを幅優先探索で求め、最小値を更新していきます。masimarock。