-4

だから、私はこの問題を抱えています。私はこのマトリックスを持っています：

1 1 1 1 1 1 1 1 1 1
1 1 0 0 0 1 0 T 0 1
H 0 0 1 1 1 0 1 1 1
1 1 0 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1

座標（3.1）からT（2.8）までのHから始まるパスを作成する必要があります。必要なもの：それ自体が迷路を表す行列A [1..M、1..N]を読み取るプログラムが必要です。要素[0,1]を使用し、H、T値も読み取ります。値1は壁と見なされ、通過できません。だから私は以前にこの質問を投稿しました、そして私は構文の助けが必要です。

擬似コードでそれをどう思うかはこれです：

var walkingDirection = up;
var walkingDirection1 = down;
var walkingDirection2 = right;
var walkingDirection3 = left;
while (not at T)
    if (next field in walkingDirection is not 1)
        go to next field in walkingDirection
    else if
       (next field in walkingDirection1 is not 1)
        go to next field in walkingDirection1
else if
       (next field in walkingDirection2 is not 1)
        go to next field in walkingDirection2
else if
         (next field in walkingDirection3 is not 1)
        go to next field in walkingDirection3
    end if
end while

構文を教えてください

int myArray[5][10] = { {1 1 1 1 1 1 1 1 1 1},
                       {1 1 0 0 0 1 0 T 0 1},
                       {H 0 0 1 1 1 0 1 1 1},
                       {1 1 0 0 0 0 0 0 0 1},
                       {1 1 1 1 1 1 1 1 1 1} };
int H = myArray [3][1];
int T = myArray [2][8];

if myArray [a+1][b]==1)
4

1 に答える 1

3

残念ながら、あなたのアルゴリズムはどのタイプの解決可能な迷路でも機能しません。

計画しているさまざまな段階で段階的に詳しく見ていくと、与えられたラビリンスの例では機能しないことを確認できることがわかります。

これを確認するには、例によってアルゴリズム全体を再生するのが最適です。

1 1 1 1 1 1 1 1 1 1
1 1 0 0 0 1 0 T 0 1
H 0 0 1 1 1 0 1 1 1
1 1 0 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1

ノードから開始H：

  • 最初にwhile状態を確認します。

    私たちはノードにいないTので、ループが実行されます。

  • WalkingDirectionを調べると、があることがわかります1。そのため、このブランチを取得できません。

  • 同じことがwalkingDirection1にも当てはまるので、このブランチも使用できません。

    代わりに、アルゴリズムが右にステップを作成するために入るのは、walkingDirection2ブランチです。

  • すでにwalkingDirection2ブランチにアクセスしたため、walkingDirection3はチェックされなくなりました。

  • 制御フローはwhileループの終わりに到達します。

    ここでも、条件を確認する必要があります。まだノードTにないため、続行する必要があります。

    ...。

この方法で例を段階的に再生し続けると、すぐに問題が見つかります。*これは、次の図でマークされている行です。

1 1 1 1 1 1 1 1 1 1
1 1 * 0 0 1 0 T 0 1
H 0 * 1 1 1 0 1 1 1
1 1 0 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1

アルゴリズムがダンジョンのその部分に入ると、アルゴリズムは継続的に上下に移動します。

  • まだ歩くことができる間にwalkDirectionブランチを取ります。

  • 1つのwalkDirectionがダウンしているwalkDirection1で一歩踏み出すと、次の実行で方向転換するためにブロックされます。これで、walkDirectionは再び歩行可能になります。

... じゃあ何をすればいいの？

考えられる方向をテストすることは一般的に悪い考えではありませんが、実際には、テストして最良のものを期待する以外に選択肢はありませんが、アルゴリズムにはある種のメモリがありません。

それが円を描くのを防ぐために、それはそれがすでにそのオプションを検査したことを検出できなければならないでしょう、あるいはもっと良いことに興味深い場所を「覚えている」でしょう。まだテストされていない可能性を提供するもの。

最も効率的なバージョンではありませんが、非常に単純なアイデアは、すでに検査されたすべてのフィールドのリストを保持することです。すでに訪問したすべてのフィールドの記録を保持して、次のようなことを言います。フィールドはまあまあの位置にあり、私はフィールドからそこに来たので、同じエラーを何度も繰り返すのを防ぐことができます。

次のようなことを思い出して、隣のフィールドにすでに入力しているために検査できるすべての潜在的な候補者の2番目のリストを保持します。その時、あなたは最も興味深い分野を調べ続けることができるはずです。

概要

これまでに与えられたアイデアを要約すると、アルゴリズムは2つの関数に要約できます。

次のfield（）

これまでに見たフィールドのリストから1つのフィールドを取得します。

すでに検査済みの場合は、再度検査する価値がないため、廃棄してください。次のいずれかになるまで、検査済みフィールドを破棄し続けます。

  • あなたのリストは空になります：迷路の解決策はありません

    その後、プログラムを終了するだけです。

  • 今まで検査されていないフィールドを見つけます。

    この場合、それをinspect（）します。

。

field（）を検査します

すでにノードにいるかどうかを確認しますT

  • はいの場合-ダンジョンから脱出できたので、「フーレイ」と声を出して歌ってください。

    そうそう、ここでプログラムを終了できます。

  • そうでない場合

    あなたがどこから来たかを思い出しながら、検査されたフィールドのリストに新しいレコードを入力します。

    隣接するすべてのフィールドに到達可能かどうか、およびそれらがすでに検査されているかどうかを確認します。

    • それらが到達可能であるが検査されていない場合は、これまでに見た興味深いフィールドのリストにそれらを追加して、どのフィールドからそれらを見たかを覚えておいてください。

      次にnext_field（）を続行します

。

このように、プログラムの開始後に実行する必要があるのは、フィールドを検査（）Hして結果を待つことだけです。

...も参照してください

より高い賭け金を目指して、あなたは以下の資料のいずれかを調べたいと思うかもしれません：

于 2013-03-27T08:22:47.010 に答える