Java 2D数组从A点到B点有障碍物的最短路径

Question

目标:找到到达目的地所需的最少移动量。

场景:在 8*8 的 2D 数组中，元素如下:

*......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++;              
                }
            }
        }   
    }
}

它的工作是找到到达目的地所需的“最短”步数，但它会将任何/障碍物视为可以移动到的空单元格。

我目前无法找到一种编码方式，使其能够识别下一步 Action 的正确决定。

我正在考虑使用数组列表和一些算法，但是我尝试阅读一些算法，例如 Dijkstra's algorithm但这看起来真的很令人困惑，有人可以帮助我以一种非常简单的方式理解它并在java中实现它吗？

//-(对不起我的编码能力，我还是个初学者)-

Answer 1

您不需要任何特殊的算法来完成此任务，只需在图中进行广度优先搜索即可。考虑在 1 步中可到达的点作为图形的第一级，在 2 步中可到达的点(这些点连接到任何第一级点，但不连接到源点)作为第二级，等等。

首先访问从源点可直接到达的点，然后访问二级点，然后访问三级点。您可以通过将节点存储在列表中来实现此目的。首先，您访问源，并将相邻节点推到列表的末尾。然后，您访问列表中的每个节点，并将它们的相邻节点推到列表的末尾(如果它们目前不在列表中)。一旦到达目标节点，就完成了。可以存储每个节点的级别，也可以存储前面的节点，这样就可以找到从目标节点向后的路径。

需要注意的一件重要事情:不要在您的列表中添加障碍物，这样就不会有路线穿过该点。