20x20の盤面があり、盤面のいくつかのセルにはブロックが乗っている。
スタートから、以下のルールに従い石を動かして、ゴールを10手以内に通過させる事が出来るか判定せよ。
石は、4方向の内、ブロックが隣接して無い方向に動かすことが出来、ブロックにぶつかるまですべって移動していく。
石がブロックにぶつかると、石はブロックの手前のマスで止まり、そのブロックは壊れて無くなってしまう。
盤面からはみ出すとゲームオーバー。

DFSで解けて、BFSで解けない問題。
DFSだと、計算時間は、ステップ数(4^10) * 滑った距離(W+H)。メモリは、盤面(WxH)+DFSの深さ(10)。
BFSだと、計算時間は、ステップ数(4^10) * (滑った距離(W+H)+盤面セーブ(W*H))。メモリは、ステップ数(4^10)*盤面(W*H)。
この様に、計算量、メモリ使用量共に、DFSが有利である。
DFSの計算時間が少なくて済むのは、DFSの途中に盤面の書き換えが、O(1)で出来るからである。
BFSで計算時間を減らすには、壊れたブロックの座標のみを覚えて、盤面セーブにかかるコストを手数(10)まで落とすなどの工夫が必要になる。

3009.cpp