- ベストアンサー
C言語でBMPの迷路を解く。
こんにちは。私は30代の男性です。 先日はCSVファイルの読み取りについて投稿しましたが、無事解決できました。アドバイスを下さった方々にはお礼申し上げます。 次は、「BMPファイルで書かれた迷路を解く」というようなことを試みています。下がイメージ図になりますが、「□は白」で「■は黒」で「※(ゴール)は青」とします。■が道で■しか進めず、他の道とは交差しない一本道であるとします。表記の都合上、下記だとスペースがありますが、実際はもちろん■は繋がっていますし「□」は白なので、実際は何もみえません。 0 ｘ→ ｙ■□□□□□□□□□□□□ ↓■□□□□□□□□□□□□ ■□□□※■■□□□□□□ ■□□□□□■□□□□□□ ■□■■■■■□□□□□□ ■□■□□□□□□□□□□ ■■■□□□□□□□□□□ 下記のような図を一つ一つ進みながら、左上の座標をx,y=(0,0)として一つ一つ座標を表示しながら進み、「※(青)」で「ゴール」と表示するには、どのようにしたらよいでしょうか？ BMPの画像は、交差しない一本道の画像ならどのような画像でも対応できるようにしたいのですが、上下左右どのような動きもしなくてはならないので、どのような条件でどのようにコーディングしたらいいのかわからず悩んでいます。 どなたかよきアドバイスをお願い致します。
- みんなの回答 （3）
- 専門家の回答
質問者が選んだベストアンサー
★交差しない一本道なら。 ・いろいろな方法で一本道の迷路は解けると思います。 基本的には、回答者 No.2 さんと同じになりますね。 進んできた方向以外の『方向に進む』です。 ・そこでアイディアを１つ出します。 (1)まず、現在進んでいる方向を変数で管理します。(左=4,右=6,上=8,下=2など) (2)現在位置を中心に進んできた方向以外の３方向の『■』を調べます。 (3)見つかった方向を進んでいく方向変数に保存してから移動します。 ・上記の３方向を調査して進む処理を繰り返せば、一本道の迷路は解けます。 ただし、外周の壁は進めないと調査する必要があります。この辺は別関数で『壁』チェックの 処理を行います。このチェックと３方向のチェックを合成した結果を上記の(3)の進んで行く 処理に返します。 その他: ・アルゴリズムを簡略化するならば、外周のチェック関数を作らずに『必ず外周がある』という BMPファイルを用意します。こうすれば外周チェック関数は必要なく、進んできた方向以外の ３方向だけ『■』を調べれば良いことになります。 ・下に外周も必ず壁となるようにした場合のイメージです。→『●』がスタート地点です。 □□□□□□□□□□□□□□□ ｙ□●□□□□□□□□□□□□□ ↓□■□□□□□□□□□□□□□ □■□□□※■■□□□□□□□ □■□□□□□■□□□□□□□ □■□■■■■■□□□□□□□ □■□■□□□□□□□□□□□ □■■■□□□□□□□□□□□ □□□□□□□□□□□□□□□ ・あと現在の位置も変数で管理する必要がありますね。 そのほか、調査する関数を再帰的やループ処理などで進む方向定数を配列データに保存して、 一気に移動＆表示ルーチンで処理させるなど仕組みも面白そうです。 ・今後、一本道以外の迷路を探索する場合は、調査する関数を再帰的に処理すれば、枝分かれしている 迷路にも対応できると思います。→この場合は、一気にゴールまで迷路を解析して進む方向を配列など に保存していきます。その後、表示ルーチンで順番にデータを読み出していけば良いでしょう。 なお、一本道の迷路では再帰処理する必要は特にありませんが、枝分かれ迷路にも対応するような実装 方法を記述しておくのもいいかも。 ・以上。おわり。→今後の迷路問題の参考にどうぞ。
その他の回答 (2)
- tatsu99
- ベストアンサー率52% (391/751)
現在点の周囲に最大２点の黒点が存在します。そのうち、一点は、かつて進んできた点になります。そうでない方の一点が進むべ点になります。 次の点に移動する時、現在の点の位置を記憶し、次の点で判定をするとき、そのかつて進んできた点（直前に記憶した現在の点）を除いた、黒点に進んでは、いかがでしょうか。
お礼
ご回答ありがとうございます。 >次の点に移動する時、現在の点の位置を記憶し、次の点で判定をするとき、そのかつて進んできた点（直前に記憶した現在の点）を除いた、黒点に進んでは、いかがでしょうか。 なるほど。ポインタを使って解決できそうですね。ありがとうございました。
- nac03056
- ベストアンサー率48% (203/419)
この黒の通路はつながっている部分以外は最低１個の白を挟んでいるものとして、現在位置の周囲を調べ黒のほうに進み、さっきいた場所を白に塗りつぶすという動作を続ければ（実際に色を消してはまずいなら事前に別のテーブルに複写しておけばいいでしょう）最後にはゴールできるはずです。 どうでしょうか？
お礼
早速のご回答、ありがとうございます。 >さっきいた場所を白に塗りつぶすという動作を続ければ（実際に色を消してはまずいなら事前に別のテーブルに複写しておけばいいでしょう）最後にはゴールできるはずです。 さっきいた場所を白にするなんて、思いつきませんでした！ これはいいアドバイスですね。ありがとうございました！
お礼
Oh-Orange様 いつもご回答頂き、ありがとうございます。 詳しい手順をお教え頂き、ありがとうございます。やらねばならない処理はいろいろとありそうですね。参考にさせて頂きます。ありがとうございました。