おはようございます。

午前中から記事を書いていきたいと思います。

今回記事は、パソコン甲子園本選出場が決まっていたのですが、今まで競技に対して準備する期間がありませんでした。

プロコンやら弥生祭やら・・・。まあ、それは置いておいて、後１週間弱あるので、できることをやっていこうと思います。

今日、ごにょごにょしたのは、迷路の解を見つけるプログラムです。

少し長くなると思い、２回に分けたいと思います。

解説をするとかなり長くなってしまいそうなので、アルゴリズムに関しては結果だけにさせてもらいます。

まず、第１は再帰による解を見つける、第２は幅優先探索による探索で最短距離を求めたいと思います。

再帰でも求められないこともないですが、迷路が大きくなってくると帰ってこなくなるので、やめましょうｗ

 

まず、これは５x５の正方形の迷路です。

２つ目の迷路は解が見つかってないのがわかります。

実行速度は大して気になりません。

次は、１０ｘ１０の正方形になります。

今回は４つです。最初の３つは、ほぼ一瞬で解が見つかりました。

しかし、最後の一つは^Cとなっています。

実行した後に気づいたのですが、１０ｘ１０の迷路の全探索になってしまうので、馬鹿みたいに時間がかかりそうだったので、途中で処理をやめました。ｗ

人の目で見る分には最後の問題はとても簡単なのですが、プログラムからしてみると、いやな問題ですね！

最後に１５ｘ１５です。

これらも特に時間に気にすることなく解が出ました。１秒もかかっていません。

後ろ二つは解が見つかっていませんが、１０ｘ１０の最後の問題より早く解が出ます。

ぱっとみ複雑で、枝分かれしていても解があるかどうかだけなので、比較的早く帰ってきました。

最後に。。。。。

再帰はとても強いアルゴリズムです。いろんなところで使われています。

使い方を間違えると、かなり面倒ですが、コツをつかむと友達になれます。

迷路なんか普通に解いてたら、気が狂ってしまいますよｗｗｗｗｗ

マインスイーパーのホワーンって消えていくやつもそれで実装しましたよ！！！

どの向きにどれくらいあるかわからないって時に便利なんですかね！？

私もまだまだ初心者なのでなんとも・・・。

以上

参考にしたい方はどぞ、大したものではありません。

ソースコードとデータ