使用二維數組和堆棧在java中構建迷宮

Question

我需要使用二維數組和堆棧構建一個迷宮。數組大小是固定的。起點是（0,0）。數組應該從文件中讀取，但在這個例子中，我假定值只是爲了說清楚。

我似乎無法找到一個合適的算法，讓我通過二維數組並保存我的路徑到堆棧。如果我卡在當前行中，那會讓我回到上一行。 PS：1是牆壁，0是路徑。的問題，需要通過用戶的輸入陣列，但我爲了簡單

赫雷什提供的一個陣列：

0 1 0 0 0 
0 1 0 0 0 
0 0 0 0 0 
1 1 1 0 0 
0 1 0 0 0 

我需要從位置（0,0）開始和出口應在最後行。如果我陷入困境，我需要走上另一條路;那是彈出堆棧。

這就是我想出了：

public class Maze { 

    Maze currentPos = new Maze(); 

    int position = maze[0][0]; 

    public Maze() 
    { 
    } 

    public Maze(Maze currentPos) 
    { 
    this.currentPos = currentPos; 
    position = maze[0][0]; 
    } 
    Stack stack = new Stack(); 

    public static int[][] maze = new int[][] { 
    {0,1,0,0,0}, 
    {0,1,0,0,0}, 
    {0,0,0,0,0}, 
    {1,1,1,0,0}, 
    {0,1,0,0,0} 
    }; 

    public boolean UP (int i, int j) 
    { 
    if (maze [i-1][j] == 0) 
     return true; 
    return false; 
    } 

    public boolean DOWN (int i, int j) 
    { 
    if (maze [i+1][j] == 0) 
     return true; 
    return false; 
    } 

    public boolean RIGHT(int i,int j) 
    { 
    if (maze [i][j+1] == 0) 
     return true; 
    return false; 
    } 

    public boolean LEFT(int i,int j) 
    { 
    if (maze [i][j-1] == 0) 
     return true; 
    return false; 
    } 

    public boolean isExit (int i, int j) 
    { 
    if (j == 6) 
     return true; 
    return false; 
    } 

    public void setPosition(int i , int j) 
    { 
    position = maze[i][j]; 
    } 

    public void solve() 
    { 
    for (int i=0; i<maze.length; i++) 
    { 
     for (int j=0; j<maze.length; j++) 
     { 
     while(! currentPos.isExit(i,j)); 
     { 
      if (currentPos.DOWN(i,j)) stack.push(i+1,j);  
      if (currentPos.LEFT(i,j)) stack.push(i,j-1);      
      if (currentPos.RIGHT(i,j)) stack.push(i,i+1); 
      if (currentPos.UP(i,j)) stack.push(i-1,j); 
     }     
     }   
    } 
    } 
} 

類棧是一樣的一個在java.util.Stack中，並用同樣的方法包括：（彈出，推）

Answer 1

這裏什麼讓你開始：

import java.util.ArrayList; 
import java.util.List; 
import java.util.Stack; 

public class Maze { 

    //keep reference to start point 
    int startRow, startCol; 

    //keep reference to addresses (row, col) that has been checked 
    List<Integer[]> visited; 

    //a stack that represents the path (solution) 
    Stack<Integer[]> path; 

    public Maze(int startRow, int startCol) { 

     this.startRow = startRow; //add: check input validity 
     this.startCol = startCol; 
     visited = new ArrayList<>(); 
     path = new Stack<>(); 
    } 

    public static int[][] mazeValues = new int[][] { 
     {0,1,0,0,0}, 
     {0,0,0,1,0}, 
     {1,1,1,0,0}, 
     {1,1,1,0,1}, 
     {0,0,0,0,0} 
    }; 

    void solve(){ 

     boolean isSolved = solve(startRow, startCol); 
     if(isSolved) { 
      pathFound(); 
     } else { 
      noPathFound(); 
     } 
    } 


    private boolean solve(int row, int col) { 

     //check if target found 
     if(isTargert(row,col)) { 
      //add target to path 
      path.push(new Integer[]{row,col}); 
      return true; 
     } 

     //check if address is a wall 
     if(isWall(row,col)) { 
      return false; 
     } 

     //check if visited before 
     if(isVisited(row, col)) { 
      return false; 
     } 

     //mark as visited 
     visited.add(new Integer[]{row,col}); 

     //add to path 
     path.push(new Integer[]{row,col}); 

     //check all neighbors (allows diagonal move) 
     for (int rowIndex = row-1; rowIndex <= (row+1) ; rowIndex++) { 

      for (int colIndex = col-1; colIndex <= (col+1) ; colIndex++) { 

       if((rowIndex == row) && (colIndex == col)) {//skip current address 
        continue; 
       } 

       if(! withInMaze(rowIndex, colIndex)) { 
        continue; 
       } 

       if(solve(rowIndex, colIndex)) { 
        return true; //solution found 
       } 
      } 
     } 

     //solution not found after checking all neighbors 
     path.pop(); //remove last from stack; 
     return false; 
    } 

    //check if address is a target 
    private boolean isTargert(int row, int col) { 
     //target set to last row/col. Change taget as needed 
     return (row == (mazeValues.length-1))&& (col == (mazeValues[0].length -1)) ; 
    } 

    //check if address is a wall 
    private boolean isWall(int row, int col) { 

     return mazeValues[row][col] == 1; 
    } 

    private boolean isVisited(int row, int col) { 

     for (Integer[] address : visited) { 

      if((address[0]==row) && (address[1]==col)) { 
       return true; 
      } 
     } 
     return false; 
    } 

    //return true if rowIndex, colIndex are with in mazeValues 
    private boolean withInMaze(int rowIndex, int colIndex) { 

     return (rowIndex < mazeValues.length)&& (rowIndex >= 0) 
       &&(colIndex < mazeValues[0].length) && (colIndex >=0); 
    } 

    private void noPathFound() { 
     System.out.println("No path found............"); 

    } 

    private void pathFound() { 

     System.out.println("Path found"); 
     for (Integer[] address : path) { 
      int row = address[0]; int col = address[1]; 
      System.out.println("Address: "+ row +"-"+ col 
           +" value: "+ mazeValues[row][col]); 
     } 
    } 

    public static void main(String[] args) { 

     Maze maze = new Maze(0,0); 
     maze.solve(); 
    } 
} 

對於一般的迷宮尋路算法，我建議先從Breadth-first search