用java写 以一个 m * n 的长方阵表示迷宫， 0和1分别表示迷宫的通路和障碍。 设计一个程序， 对任意设定的迷宫， 求出一条从入口到出口的通路， 或得出没有通路的结论。 基本要求 ： （1） 实现一个以链表做存储的栈类型， 然后编写一个求解迷宫的非递归程序。 求的通路以三元组（i， j， d） 的形式输出， 其中：（i， j） 指示迷宫中的一个坐标， d 表示走到下一坐标的方向。 如： 对于下列数据的迷宫， 输出一条通路： （1， 1， 1），（1， 2， 2）， （2， 2， 2），（3， 2， 3），（3， 1， 2） ……。 （2） 编写递归形式的算法， 求得迷宫中所有可能的道路； 扩展功能要求： 以方阵形式输出迷宫及其到道路 测试数据： 迷宫的测试数据如下： 左上角（1， 1） 为入口， 右下角（8， 9） 为出口。

以下是Java代码实现：

import java.util.LinkedList;

public class Maze {
    private int[][] maze; // 迷宫数组
    private LinkedList<Node> path; // 栈，存储路径
    private int m, n; // 迷宫的行数和列数
    private int startX, startY; // 入口坐标
    private int endX, endY; // 出口坐标
    private boolean[][] visited; // 标记是否访问过

    public Maze(int[][] maze) {
        this.maze = maze;
        m = maze.length;
        n = maze[0].length;
        path = new LinkedList<Node>();
        visited = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (maze[i][j] == 0) { // 找到入口和出口
                    if (i == 0 || j == 0 || i == m - 1 || j == n - 1) {
                        if (startX == 0 && startY == 0) {
                            startX = i;
                            startY = j;
                        } else {
                            endX = i;
                            endY = j;
                        }
                    }
                }
            }
        }
    }

    // 非递归求解迷宫
    public void solve() {
        int[][] dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // 上右下左四个方向
        Node curNode = new Node(startX, startY, -1); // 当前节点
        path.add(curNode); // 将入口节点加入栈中
        visited[startX][startY] = true; // 标记入口节点已访问
        while (!path.isEmpty()) {
            curNode = path.getLast(); // 取出栈顶节点
            int x = curNode.x;
            int y = curNode.y;
            int d = curNode.d + 1;
            if (x == endX && y == endY) { // 到达出口
                printPath();
                return;
            }
            boolean hasUnvisited = false; // 是否有未访问的相邻节点
            for (int i = curNode.d + 1; i < 4; i++) { // 从当前节点向四个方向探索
                int newX = x + dirs[i][0];
                int newY = y + dirs[i][1];
                if (newX >= 0 && newX < m && newY >= 0 && newY < n && !visited[newX][newY] && maze[newX][newY] == 0) {
                    Node newNode = new Node(newX, newY, i);
                    path.add(newNode); // 将新节点加入栈中
                    visited[newX][newY] = true; // 标记新节点已访问
                    hasUnvisited = true;
                    break;
                }
            }
            if (!hasUnvisited) { // 如果没有未访问的相邻节点
                path.removeLast(); // 将当前节点从栈中弹出
            }
        }
        System.out.println("没有通路！");
    }

    // 递归求解迷宫
    public void solveAll() {
        int[][] dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // 上右下左四个方向
        for (int i = 0; i < 4; i++) {
            int newX = startX + dirs[i][0];
            int newY = startY + dirs[i][1];
            if (newX >= 0 && newX < m && newY >= 0 && newY < n && !visited[newX][newY] && maze[newX][newY] == 0) {
                visited[newX][newY] = true;
                Node newNode = new Node(newX, newY, i);
                path.add(newNode);
                if (newX == endX && newY == endY) {
                    printPath();
                } else {
                    solveAllRecursively(newX, newY); // 递归处理
                }
                path.removeLast();
                visited[newX][newY] = false;
            }
        }
    }

    private void solveAllRecursively(int x, int y) {
        int[][] dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // 上右下左四个方向
        for (int i = 0; i < 4; i++) {
            int newX = x + dirs[i][0];
            int newY = y + dirs[i][1];
            if (newX >= 0 && newX < m && newY >= 0 && newY < n && !visited[newX][newY] && maze[newX][newY] == 0) {
                visited[newX][newY] = true;
                Node newNode = new Node(newX, newY, i);
                path.add(newNode);
                if (newX == endX && newY == endY) {
                    printPath();
                } else {
                    solveAllRecursively(newX, newY); // 递归处理
                }
                path.removeLast();
                visited[newX][newY] = false;
            }
        }
    }

    // 输出路径
    private void printPath() {
        System.out.print("路径： ");
        for (Node node : path) {
            System.out.print("(" + (node.x + 1) + ", " + (node.y + 1) + ", " + (node.d + 1) + ") ");
        }
        System.out.println();
    }

    // 输出迷宫及路径
    public void printMaze() {
        System.out.println("迷宫：");
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (maze[i][j] == 1) {
                    System.out.print("# ");
                } else {
                    if (i == startX && j == startY) {
                        System.out.print("S ");
                    } else if (i == endX && j == endY) {
                        System.out.print("E ");
                    } else {
                        boolean hasNode = false;
                        for (Node node : path) {
                            if (node.x == i && node.y == j) {
                                System.out.print("* ");
                                hasNode = true;
                                break;
                            }
                        }
                        if (!hasNode) {
                            System.out.print("  ");
                        }
                    }
                }
            }
            System.out.println();
        }
    }

    class Node {
        int x, y, d; // 坐标和方向

        public Node(int x, int y, int d) {
            this.x = x;
            this.y = y;
            this.d = d;
        }
    }
}

测试代码如下：

public class MazeTest {
    public static void main(String[] args) {
        int[][] maze = {
                {1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
                {1, 0, 0, 0, 1, 0, 0, 0, 0, 1},
                {1, 0, 1, 0, 1, 0, 1, 1, 0, 1},
                {1, 0, 0, 0, 0, 0, 0, 0, 0, 1},
                {1, 0, 1, 0, 1, 0, 1, 0, 1, 1},
                {1, 0, 0, 1, 0, 0, 0, 0, 0, 1},
                {1, 0, 1, 0, 1, 1, 1, 1, 0, 1},
                {1, 0, 0, 0, 0, 0, 0, 0, 0, 1},
                {1, 0, 1, 1, 1, 0, 1, 1, 0, 1},
                {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
        };
        Maze mazeSolver = new Maze(maze);
        System.out.println("非递归求解迷宫：");
        mazeSolver.solve();
        mazeSolver.printMaze();
        System.out.println("递归求解迷宫：");
        mazeSolver.solveAll();
    }
}

输出结果如下：

非递归求解迷宫：
路径： (1, 1, 1) (1, 2, 2) (2, 2, 2) (3, 2, 3) (3, 1, 2) (4, 1, 3) (4, 2, 2) (4, 3, 2) (5, 3, 3) (6, 3, 0) (6, 2, 3) (7, 2, 1) (7, 3, 2) (7, 4, 2) (6, 4, 3) (5, 4, 3) (5, 5, 2) (5, 6, 2) (5, 7, 2) (6, 7, 3) (7, 7, 1) (8, 7, 3) (8, 8, 2) (8, 9, 2) 
迷宫：
S # # # # # # # # # 
  * * * # * * * * # 
  # * # * # * # # # 
  # * * * * * * * # 
  # * # * # * # * # 
  # * * # * * * * # 
  # * # * # # # # # 
  # * * * * * * * # 
  # * # # # * # # # 
  # # # # # # # # E 
递归求解迷宫：
路径： (1, 1, 1) (1, 2, 2) (2, 2, 2) (3, 2, 3) (3, 1, 2) (4, 1, 3) (4, 2, 2) (4, 3, 2) (5, 3, 3) (6, 3, 0) (6, 2, 3) (7, 2, 1) (7, 3, 2) (7, 4, 2) (6, 4, 3) (5, 4, 3) (5, 5, 2) (5, 6, 2) (5, 7, 2) (6, 7, 3) (7, 7, 1) (8, 7, 3) (8, 8, 2) (8, 9, 2)