0

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

场景：在 2D Array 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++;              
                }
            }
        }   
    }
}

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

我目前无法找到一种方法来对其进行编码，使其能够识别下一个动作的正确决定。

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

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

4

1 回答 1

1

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

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

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

于 2013-02-02T18:07:15.667 回答