Java数据结构:栈(迷宫求解)（用栈解决迷宫问题的数据结构课程设计）

迷宫求解是一个经典的搜索问题，可以使用深度优先搜索（DFS）算法来解决。DFS算法需要回溯，而栈（Stack）数据结构则非常适合用于实现回溯。

在迷宫求解中，我们可以将迷宫视为一个二维网格，每个格子要么是墙壁（不可通过），要么是空地（可通过）。我们的目标是找到一条从起点到终点的路径。

使用栈进行迷宫求解的大致步骤如下：

1，初始化栈，将起点位置压入栈中，并标记起点为已访问。

2，进入循环，当栈不为空时执行以下步骤：a. 从栈中弹出一个位置。b. 检查当前位置是否是终点，如果是，则找到路径，结束循环。c. 如果不是终点，则尝试当前位置的四个方向（上、右、下、左）。d. 对于每个方向，检查新位置是否在迷宫内且是空地且未被访问过。如果满足条件，将新位置压入栈中，并标记为已访问。

3，如果循环结束仍未找到路径，则输出无解。

代码示例（可直接运行查看结果）：

import java.util.Stack;  
  
public class MazeSolver {  
    private static final int EMPTY = 0; // 空地  
    private static final int WALL = 1; // 墙壁  
    private static final int VISITED = 2; // 已访问  
    private static final int[][] DIRECTIONS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 上下左右四个方向  
  
    private int[][] maze; // 迷宫二维数组  
    private int rows; // 迷宫的行数  
    private int cols; // 迷宫的列数  
    private int startRow; // 起点行坐标  
    private int startCol; // 起点列坐标  
    private int endRow; // 终点行坐标  
    private int endCol; // 终点列坐标  
  
    public MazeSolver(int[][] maze, int startRow, int startCol, int endRow, int endCol) {  
        this.maze = maze;  
        this.rows = maze.length;  
        this.cols = maze[0].length;  
        this.startRow = startRow;  
        this.startCol = startCol;  
        this.endRow = endRow;  
        this.endCol = endCol;  
    }  
  
    public boolean solve() {  
        Stack<int[]> stack = new Stack<>();  
        maze[startRow][startCol] = VISITED; // 标记起点为已访问  
        stack.push(new int[]{startRow, startCol});  
  
        while (!stack.isEmpty()) {  
            int[] current = stack.pop();  
            int row = current[0];  
            int col = current[1];  
  
            // 如果当前位置是终点，则找到路径  
            if (row == endRow && col == endCol) {  
                return true;  
            }  
  
            // 尝试四个方向  
            for (int[] direction : DIRECTIONS) {  
                int newRow = row + direction[0];  
                int newCol = col + direction[1];  
  
                // 检查新位置是否在迷宫内且是空地且未被访问过  
                if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols && maze[newRow][newCol] == EMPTY) {  
                    maze[newRow][newCol] = VISITED; // 标记新位置为已访问  
                    stack.push(new int[]{newRow, newCol}); // 将新位置压入栈中  
                }  
            }  
        }  
  
        // 栈为空时仍未找到路径  
        return false;  
    }  
  
    public void printMaze() {  
        for (int i = 0; i < rows; i++) {  
            for (int j = 0; j < cols; j++) {  
                if (maze[i][j] == EMPTY) {  
                    System.out.print("  ");  
                } else if (maze[i][j] == WALL) {  
                    System.out.print("##");  
                } else {  
                    System.out.print("**");  
                }  
            }  
            System.out.println();  
        }  
    }  
  
    public static void main(String[] args) {  
        // 定义迷宫  
        int[][] maze = {  
            {0, 0, 0, 0, 0},  
            {1, 1, 0, 1, 0},  
            {0, 0, 0, 0, 0},  
            {0, 1, 1, 1, 1},  
            {0, 0, 0, 0, 0}  
        };  
  
        // 定义起点和终点  
        int startRow = 0;  
        int startCol = 0;  
        int endRow = 4;  
        int endCol = 4;  
  
        // 创建迷宫求解器并求解  
        MazeSolver solver = new MazeSolver(maze, startRow, startCol, endRow, endCol);  
        boolean found = solver.solve();  
  
        // 输出结果  
        if (found) {  
            System.out.println("找到路径！");  
            solver.printMaze();  
        } else {  
            System.out.println("未找到路径。");  
        }  
    }  
}