使用二维数组和堆栈在 java 中构建迷宫

Question

我需要使用二维数组和堆栈构建迷宫。数组大小是固定的。起点是 (0,0)。该数组应该从文件中读取，但在这个例子中，我假设值只是为了让事情更清楚。

我似乎找不到合适的算法让我遍历二维数组并将我的路径保存到堆栈。如果我卡在当前行，这会让我回到上一行。 PS: 1是墙，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);
        }                   
      }         
    }
  }
}

class 堆栈与 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

开始

使用二维数组和堆栈在 java 中构建迷宫

Constructing Mazes in java using 2D array and stacks

java

arrays

stack

maze

multidimensional-array