java - 使用 2D 数组和堆栈在 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 中的相同，并且包含相同的方法(pop、push)

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 开始