Java 2D陣列從A點到障礙物的最短路徑

目的：找到到達目的地所需的最少移動量。Java 2D陣列從A點到障礙物的最短路徑

方案：在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++;    
       } 
      } 
     } 
    } 
}

它找到到達目的地所需的「最短」的步驟量的工作但它會考慮什麼/障礙，空細胞它可以移動到。

我目前無法想出一種方式來編碼，以便能夠識別下一次移動的正確決定。

我正在考慮使用數組列表和一些算法，但我嘗試讀取一些算法，如Dijkstra's algorithm，但它似乎很混亂，任何人都可以幫助我以非常簡單的方式理解它在java中的實現？

// - （對不起我的編程技能，我還是個初學者） -

來源

2013-02-02 NoCakeNoCode

Google for A * -Algorithm – MrSmith42

你並不需要爲這個任務的任何特殊的算法，只在圖的廣度優先搜索。考慮以1步可達到的點作爲圖的第一級，這些點可以分2步到達（這些連接到任何第一級點，但不連接到源點）作爲第二級，等等。

首先訪問從源點直接到達的點，然後訪問第二級點，然後訪問第三級點。您可以通過將節點存儲在列表中來實現此目的。首先訪問源代碼，並將鄰居節點推到列表的末尾。然後，您訪問列表中的每個節點，並將它們的相鄰節點推到列表的末尾（如果它們不在列表中）。一旦你到達目標節點，你就完成了。您可以存儲每個節點的級別，還可以存儲前一個節點，以便從目標節點向後找到路徑。

一個重要的事情要注意：不要給列表添加障礙物，這樣就不會有路線穿過那個點。

來源

2013-02-02 18:07:15

Java 2D陣列從A點到障礙物的最短路徑

回答

相關問題