在迷宮中打印最短路的長度

Question

我試圖讓Java程序在迷宮中找到最短的路，並打印出路的長度。

。是一種方式，'x'是障礙。

如果I輸入

....xxx. 
x.x....x 
xxx..... 
x......x 
...xxxxx 
........ 
xxx..... 
xx...... 

輸出是無限：

0, 0 
0, 1 
1, 1 
0, 1 
1, 1 
0, 1 
1, 1 
0, 1 
1, 1 
0, 1 
1, 1 
0, 1 
1, 1 
0, 1 
... 

和java.lang.StackOverflowError的發生。

正確的輸出必須

0, 0 
0, 1 
1, 1 
0, 1 
0, 2 
0, 3 
1, 3 
2, 3 
3, 3 
3, 4 
3, 5 
3, 6 
3, 5 
3, 4 
3, 3 
3. 2 
4, 2 
5, 2 
5, 3 
6, 3 
7, 3 
7, 4 
7, 5 
7, 6 
7, 7 
16 

如何修改我的代碼，並得到一個正確的答案？ 或者我應該使用什麼算法來創建一個新的代碼？ 我很困惑..

我試過很多次，但我不能得到正確的答案T_T PLZ幫我

import java.util.Scanner; 

public class ShortestMazeWay 
{ 
    static int count=0; 
    static int[] result = new int[10000]; // save the move direction 
    static int[][] find = new int[8][8]; 
    static int[][] maze = new int[8][8]; // 0 = can go, 1 = can not go 

    public static void main(String[] args) 
    { 
     Scanner sc = new Scanner(System.in); 

     for(int i=0; i<8; i++) 
     { 
      String str = sc.nextLine(); 

      for(int j=0; j<8; j++) 
      { 
       if(str.charAt(j)=='.') 
        maze[i][j]=0; 
       else 
        maze[i][j]=1; 
      } 
     } 

     find(0, 0); // start from (0, 0) 
    } 

    static void find(int i, int j) 
    { 
     find[i][j] = 1; // 0 = can go, 1 = can not go 
     System.out.println(i+", "+j); // to check the way 

     if(i==7 && j==7) // the end point is (7, 7) 
      System.out.println(count); 

     else 
     { 
      count++; 

      if(i+1<8 && maze[i+1][j]!=1 && find[i+1][j]==0) // ↓ 
      { 
       result[count] = 1; 
       find[i][j] = 0; 
       find(i+1, j); 
      } 

      else if(j+1<8 && maze[i][j+1]!=1 && find[i][j+1]==0) // → 
      { 
       result[count] = 2; 
       find[i][j] = 0; 
       find(i, j+1); 
      } 

      else if(i-1>=0 && maze[i-1][j]!=1 && find[i-1][j]==0) // ↑ 
      { 
       if(result[count-1]==2) // if moved ↓ in previous step, 
        count--; // go back to previous position 
       else 
        result[count] = 3; 

       find[i][j] = 0; 
       find(i-1, j); 
      } 

      else if(j-1>=0 && maze[i][j-1]!=1 && find[i][j-1]==0) // ← 
      { 
       if(result[count-1]==1) // if moved → in previous step, 
        count--; // go back to previous position 
       else 
        result[count] = 4; 

       find[i][j] = 0; 
       find(i, j-1); 
      } 
     } 
    } 
} 

Answer 1

當在.的走，你需要確保你不要踩在已經踩過的.上。

要做到這一點的一種方法是留下面包屑，將.更改爲*，並記住將其更改回'。'。當你回溯。

實施例：方向順序是up，right，down，left：

*...xxx. 1 **..xxx. 2 ***.xxx. 3 ****xxx. 4 ****xxx. 5 ****xxx. 6 
x.x....x x.x....x x.x....x x.x....x x.x*...x x.x**..x 
xxx..... xxx..... xxx..... xxx..... xxx..... xxx..... 
x......x x......x x......x x......x x......x x......x 
...xxxxx ...xxxxx ...xxxxx ...xxxxx ...xxxxx ...xxxxx 
........ ........ ........ ........ ........ ........ 
xxx..... xxx..... xxx..... xxx..... xxx..... xxx..... 
xx...... xx...... xx...... xx...... xx...... xx...... 

****xxx. 7 ****xxx. 8 ****xxx. 9 ****xxx. 10 ****xxx. 11 ****xxx. 12 
x.x***.x x.x****x x.x****x x.x****x x.x****x x.x****x 
xxx..... xxx..... xxx...*. xxx...** xxx...*. xxx...*. 
x......x x......x x......x x......x x.....*x x....**x 
...xxxxx ...xxxxx ...xxxxx ...xxxxx ...xxxxx ...xxxxx 
........ ........ ........ ........ ........ ........ 
xxx..... xxx..... xxx..... xxx..... xxx..... xxx..... 
xx...... xx...... xx...... xx...... xx...... xx...... 

****xxx. 13 ****xxx. 14 ****xxx. 15 ****xxx. 16 ****xxx. 17 ****xxx. 18 
x.x****x x.x****x x.x****x x.x****x x.x****x x.x****x 
xxx..**. xxx.***. xxx.***. xxx.***. xxx****. xxx.***. 
x....**x x....**x x...***x x..****x x..****x x.*****x 
...xxxxx ...xxxxx ...xxxxx ...xxxxx ...xxxxx ...xxxxx 
........ ........ ........ ........ ........ ........ 
xxx..... xxx..... xxx..... xxx..... xxx..... xxx..... 
xx...... xx...... xx...... xx...... xx...... xx...... 

通知它步驟10和11之間如何回溯，與步驟17和18之間再次

記住：你第一次到達最後並不一定是最短的路線。您必須嘗試所有步驟的所有組合，並記住找到的最短路徑，而不僅僅是找到的第一個路徑。

有了上面使用的方向順序，這裏有完整路徑的一些例子：

First  Shortest Shortest Last  Longest 
****xxx. ****xxx. ****xxx. ****xxx. ****xxx. 
x.x****x x.x*...x x.x*...x x.x*...x x.x****x 
xxx.***. xxx*.... xxx*.... xxx*.... xxx.***. 
x.*****x x.**...x x.**...x x***...x x.*****x 
..*xxxxx ..*xxxxx ..*xxxxx **.xxxxx ***xxxxx 
..****** ..****** ..***... ****.... ******** 
xxx....* xxx....* xxx.***. xxx*.... xxx***** 
xx.....* xx.....* xx....** xx.***** xx.***** 

如此，因爲你要記住採取一切你到了結束時間全部路線，堆棧實現更好比目前使用的遞歸實現。

UPDATE：優化

有一個新的思考方式來解決問題，而不回溯，這意味着它應該會更快。

用步號替換麪包屑，即到達該位置的（最少）步數。

初始化maze與-1用於阻止（x）和Integer.MAX_VALUE開放（.），則執行以下操作：

walk(maze, 0, 0, 1); 

private static void walk(int[][] maze, int y, int x, int step) { 
    if (y >= 0 && y < 8 && x >= 0 && x < 8 && maze[y][x] > step) { 
     maze[y][x] = step; 
     walk(maze, y - 1, x, step + 1); 
     walk(maze, y + 1, x, step + 1); 
     walk(maze, y, x + 1, step + 1); 
     walk(maze, y, x - 1, step + 1); 
    } 
} 

結果是這樣的迷宮：

1 2 3 4 XX XX XX .. <-- Unreachable 
XX 3 XX 5 6 7 8 XX 
XX XX XX 6 7 8 9 10 
XX 9 8 7 8 9 10 XX 
11 10 9 XX XX XX XX XX 
12 11 10 11 12 13 14 15 
XX XX XX 12 13 14 15 16 
XX XX 14 13 14 15 16 17 

現在，您可以通過從末尾追蹤（17），找到最短路徑，進入較低編號r，直到你回到起點（1）。