六角形のタイルが敷き詰められた2次元空間の中に、長さn(<= 8)の節からなる大蛇と、k(<=100)個の岩、そしてゴールがある。
大蛇は、以下の条件を保ちながら動く事が出来る。
1. X番目の節は、存在するなら必ずX-1番目の節、X+1番目の節と隣接している。
2. ある節を動かすと、それに隣接した節は動かせない。
3. X番目の節は、X-1番目、X+1番目の節以外と隣接していない。
4. 一つのタイルに二つ以上の節を入れる事は出来ない。
5. 岩があるタイルに節を置くことが出来ない。
最短何ターンで、大蛇の頭をゴールまで持っていくが出来るか?
必ず20ターン以内でゴールまで辿り着ける事が保証されている。

幅優先探索と深さ優先探索の両方が必要となる問題。
蛇の状態から、次のターンの蛇の状態を生成するのは、深さ優先探索で書くのが良いだろう。
そして蛇がゴールに辿り着くまで、幅優先探索で、1ターンずつ、時間を進めていくのが良い。
蛇は一つ上下に進むのに4ターン、一つ左右に進むのに2ターンかかる為、頭が取りうる位置は200箇所も無いだろう。
頭の位置が決まると、次の節の位置が6通り、その次が3通り...と6*3^6 = 4374通りしかない為、90万状態。
制限時間が無い国内予選なら、これで行けると思えるはずだ。
移動の制約が付く為、実際に取りうる状態はもっと少なくなる筈。
PKUでは制限時間が厳しい為、更に頭の位置を利用した枝刈りなどが必要となる。

3008.cpp