パソコン甲子園の準備

おはようございます。

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

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

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

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

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

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

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

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

 

まず、これは5x5の正方形の迷路です。

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

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

5

次は、10x10の正方形になります。

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

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

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

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

10.1

10.2

最後に15x15です。

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

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

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

15.1

15.2

15.3

最後に。。。。。

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

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

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

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

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

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

以上

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

ソースコードとデータ

 


コメントを残す

メールアドレスが公開されることはありません。

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください