0

目的：目的地に到達するために必要な最小限の移動量を見つける。

シナリオ：次のような要素を持つ2D配列8 *8の場合：

*......B
........
****.**.
.A....*.
........
....**..
........
....*...

どこ

  • 「A」は開始点を表します。
  • 「B」は目的地を表します。
  • 「*」は障害物を表します。
  • 「。」は空のセルを表します。

現在、私は次のコードを実行しました。

import java.io.BufferedReader;
import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;

class main
{
    public static void main(String args[]) throws FileNotFoundException,IOException
    {   
        FileInputStream FS = new FileInputStream("path.in");
        DataInputStream DS = new DataInputStream(FS);
        BufferedReader buffer = new BufferedReader(new InputStreamReader(DS));

        String strLine = buffer.readLine();             
        int testCase = Integer.parseInt(strLine);

        int R,C;

        for(int i = 0;i < testCase;i++)
        {           

            strLine = buffer.readLine();                    
            String input[] = strLine.split(" ");

            R = Integer.parseInt(input[0]);
            C = Integer.parseInt(input[1]);

            char[][] array = new char[R][C];

            int sCoordX = 0;
            int sCoordY = 0;
            int eCoordX = 0;
            int eCoordY = 0;

            for(int j = 0; j < R ; j++)
            {
                strLine = buffer.readLine();        

                for(int k = 0;k < C;k++)
                {                               
                    array[j][k] = strLine.charAt(k);
                    if(array[j][k] == 'A')
                    {
                        sCoordX = j;
                        sCoordY = k;
                    }

                    if(array[j][k] == 'B')
                    {
                        eCoordX = j;
                        eCoordY = k;
                    }
                }   
            }

            boolean reached = false;
            int counter = 0;
            int posX = sCoordX;
            int posY = sCoordY;
            while(!reached)
            {
                if(array[posX][posY] == 'B')
                {
                    reached = true;
                    System.out.println("You are in goal!");
                    System.out.println(array[posX][posY]);
                    System.out.println("Number of steps:"+counter);
                }

                if(!reached && posX > eCoordX)
                {
                        posX--;
                        counter++;                  
                }
                else if(!reached && posX < eCoordX)
                {
                    posX++;
                    counter++;                  
                }

                if(!reached && posY > eCoordY)
                {
                    posY--;
                    counter++;          
                }
                else if(!reached && posY < eCoordY)
                {
                    posY++;
                    counter++;              
                }
            }
        }   
    }
}

目的地に到達するために必要な「最短」のステップ数を見つける役割を果たしますが、移動可能な空のセルとして何か/障害物を考慮します。

私は現在、次の動きの適切な決定を認識できるようにコーディングする方法を見つけることができません。

配列リストといくつかのアルゴリズムを使用することを考えていますが、ダイクストラのアルゴリズムなどのいくつかのアルゴリズムを読んでみましたが、本当に混乱しているように見えました。Javaで実装するために非常に簡単な方法で理解するのを手伝ってくれる人はいますか？

//-（コーディングスキルは申し訳ありませんが、まだ初心者です）-

4

1 に答える 1

1

このタスクには特別なアルゴリズムは必要ありません。グラフの幅優先探索のみが必要です。1ステップで到達可能なポイントをグラフの最初のレベル、2ステップで到達可能なポイント（これらのポイントは最初のレベルのポイントのいずれかに接続されていますが、ソースポイントには接続されていません）を2番目のレベルと見なします。

最初にソースポイントから直接到達可能なポイントにアクセスし、次に第2レベルのポイントにアクセスし、次に第3レベルのポイントにアクセスします。これは、ノードをリストに保存することで実現できます。まず、ソースにアクセスし、隣接ノードをリストの最後にプッシュします。次に、リスト内の各ノードにアクセスし、隣接するノードがリストにない場合は、それらのノードをリストの最後にプッシュします。ターゲットノードに到達すると、完了です。各ノードのレベルを保存できます。また、前のノードを保存できるため、ターゲットノードから逆方向のパスを見つけることができます。

注意すべき重要な点の1つは、リストに障害物を追加しないでください。そうすれば、そのポイントを横断するルートがなくなります。

于 2013-02-02T18:07:15.667 に答える