Problem D [1 of 3] ► 出典 : 泉のオリジナル問題  元ネタは PJ '92 12月号のゲームデザイン館 ► 10 マスからなるフィールドに数字のついた石がいくつかおかれている ► ゲームの目標は石を適当に動かして、すべての石を消去すること 4 7 9 Problem D [2 of 3] ► それぞれの石は、その石にかかれた数字だけ左向きまたは右向きに動く。  左右の壁にぶつかったときは跳ね返る。 ► ただし、次の操作はできない。  一番左のマスにある石を左向きに動かす。  一番右のマスにある石を右向きに動かす。 4 7 4 7 Problem D [3 of 3] ► 2 つの石が重なると、それらの石にかかれた数字の和の下 1 桁がかかれた 1 つの石になる ► 数字が 0 になればその石は消える 3 9 4 3 7 : 与えられた初期状態に対し、全部の石を消去する最短の手順を求めるプログラムを作成せよ ► 問題 Solution of Problem D [1 of 2] ► ごく典型的な幅優先探索の問題 ► 同じ状態が多数生成されるので、それらを重複して探索しないようにすること  たとえば、すでに探索した状態を集合型（STL ならば set、Java ならば HashSet など）に格納する Solution of Problem D [2 of 2] ► 細かい部分でのひっかけに注意  一番左（右）のマスにある石を左（右）向きに移動してはならない  移動したはずの石が残っている?? ► 石にかかれた数字の和が 10 の倍数でないときは絶対に消去できない  したがって、この場合は探索をしなくてよい