0

ねえ、私は地元のプログラミングコンテストに参加していて、彼らは私にこの質問をしましたが、私にはできませんでした。この質問について私を助けてください。

ファイルから迷路のサイズをロードし、次に迷路自体をロードするプログラムを作成します。迷路をモデル化するために、開始セル「。」を指定する文字「S」を使用します。これは空きセルを指定し、「＃」は壁、「F」は最後のセルです。開始セルから最終セルへのパスを見つけるプログラムを作成します。迷路の中にはコマンドに従うロボットがあると考えることができるので、次の迷路では、ロボットは次のコマンドを受け取る必要があります：上、上、右、右、下、下。

迷路1テキストファイル

5 5
#####
#...#
#.#.#
#S#T#
#####

迷路2テキストファイル

4 5
#.#.#
#.#.#
#S#T#
#####

一般的にプログラムを作成します（迷路の最大入力は最大200x200です）。

助けていただければ幸いです。私は新進気鋭の2年生なので、コードを提供していただければ、私はそれを理解でき、彼らは自分でそれをやり直します。

4

3 に答える 3

3

何を検索すればよいかわからない場合：http： //en.wikipedia.org/wiki/Pathfinding#Sample_algorithm これには多くの情報が含まれています： http ：//www.astrolog.org/labyrnth/algrithm.htm

于 2010-11-14T05:01:01.663 に答える
2

パスを見つける1つの方法：

  1. チェックするセルのキューと、そこから宛先までの各セルのステップ数を用意します。
  2. 終了セルのカウントを0に設定し、キューに追加します。
  3. キューが空でない場合：
    1. キューからセルを取得します。
    2. 空き隣接セルごとに、現在のセルのカウント+1を隣接セルのカウントと比較します。それより少ない場合、つまり隣接セルにまだカウントがない場合は、隣接セルのカウントを現在のセルのカウント+ 1に設定してから、隣接セルをキューに追加します。

キューが空になると、迷路内のすべての空きセル（宛先から到達可能）には、宛先への最短パスのステップ数が含まれます。セルにカウントがない場合、セルから宛先へのパスはありません。

開始セルにカウントがある場合、

  1. 開始セルの数を取得します。
  2. 各隣接セルのカウント（カウント-1）を確認します。1つあり、それがパスの次のステップです。そのセルへの方向を記録してから、そのセルを取得します。宛先でない場合は、そのセルで手順2を繰り返します。

迷路をロードする方法を理解するのはあなたに任せます。これはすべての簡単な部分です。

于 2010-11-14T04:35:19.483 に答える
0

コードはここに書くには多すぎますが、迷路を解決する最も一般的な方法は、一方向に出発することです。右に曲がるたびに、右に曲がります。

これは、開始と終了が周囲の4つの壁のいずれかにある限り機能することが保証されています。壁に沿って開始と終了がない迷路の場合、これは再帰的な演習です。

出発点として、それに基づいてコードごとに何を考え出すことができるかを見てください！

HTH、ジェームズ

于 2010-11-14T04:22:47.357 に答える