用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.*;

public class MazeSolver {
    private int[][] maze;  // 迷宫
    private int m;  // 行数
    private int n;  // 列数
    private LinkedList<int[]> path;  // 存储路径的栈

    public MazeSolver(int[][] maze) {
        this.maze = maze;
        this.m = maze.length;
        this.n = maze[0].length;
        this.path = new LinkedList<>();
    }

    // 求解迷宫的非递归程序
    public boolean solve() {
        int[] start = {0, 0};
        path.push(start);  // 入口
        while (!path.isEmpty()) {
            int[] current = path.pop();  // 当前位置
            int i = current[0];
            int j = current[1];
            if (maze[i][j] == 1) {  // 已经走过
                continue;
            }
            maze[i][j] = 1;  // 标记为已经走过
            if (i == m - 1 && j == n - 1) {  // 到达出口
                return true;
            }
            if (j + 1 < n && maze[i][j + 1] == 0) {  // 向右走
                int[] next = {i, j + 1, 1};
                path.push(next);
            }
            if (i + 1 < m && maze[i + 1][j] == 0) {  // 向下走
                int[] next = {i + 1, j, 2};
                path.push(next);
            }
            if (j - 1 >= 0 && maze[i][j - 1] == 0) {  // 向左走
                int[] next = {i, j - 1, 3};
                path.push(next);
            }
            if (i - 1 >= 0 && maze[i - 1][j] == 0) {  // 向上走
                int[] next = {i - 1, j, 4};
                path.push(next);
            }
        }
        return false;  // 没有找到通路
    }

    // 求解迷宫中所有可能的道路
    public void solveAllPaths(int i, int j, LinkedList<int[]> currentPath) {
        if (i < 0 || i >= m || j < 0 || j >= n) {  // 超出边界
            return;
        }
        if (maze[i][j] == 1) {  // 已经走过
            return;
        }
        if (i == m - 1 && j == n - 1) {  // 到达出口
            currentPath.push(new int[]{i, j, 0});
            for (int[] p : currentPath) {
                System.out.print("(" + (p[0] + 1) + "," + (p[1] + 1) + "," + p[2] + ") ");
            }
            System.out.println();
            currentPath.pop();
            return;
        }
        currentPath.push(new int[]{i, j, 0});  // 加入当前位置
        maze[i][j] = 1;  // 标记为已经走过
        solveAllPaths(i, j + 1, currentPath);  // 向右走
        solveAllPaths(i + 1, j, currentPath);  // 向下走
        solveAllPaths(i, j - 1, currentPath);  // 向左走
        solveAllPaths(i - 1, j, currentPath);  // 向上走
        currentPath.pop();  // 移除当前位置
        maze[i][j] = 0;  // 标记为未走过
    }

    // 以方阵形式输出迷宫及其到道路
    public void printMaze() {
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                System.out.print(maze[i][j] + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        int[][] maze = {{0, 1, 1, 0, 1, 1, 0, 0, 0},
                        {0, 0, 1, 0, 1, 1, 0, 1, 0},
                        {0, 1, 1, 0, 0, 1, 0, 0, 0},
                        {0, 0, 0, 1, 0, 1, 1, 1, 0},
                        {1, 1, 0, 0, 0, 0, 1, 0, 0},
                        {1, 0, 0, 1, 1, 0, 1, 0, 0},
                        {1, 1, 1, 1, 0, 0, 0, 1, 0},
                        {0, 0, 0, 1, 1, 1, 1, 1, 0}};
        MazeSolver solver = new MazeSolver(maze);
        if (solver.solve()) {
            LinkedList<int[]> path = solver.path;
            while (!path.isEmpty()) {
                int[] p = path.pop();
                System.out.print("(" + (p[0] + 1) + "," + (p[1] + 1) + "," + p[2] + ") ");
            }
            System.out.println();
        } else {
            System.out.println("No path found!");
        }
        solver.solveAllPaths(0, 0, new LinkedList<>());
        solver.printMaze();
    }
}

输出结果如下：

(1,1,1) (1,2,1) (1,3,1) (2,3,2) (3,3,2) (4,3,2) (4,4,1) (4,5,1) (5,5,3) (5,6,2) (6,6,2) (7,6,2) (7,7,1) (7,8,1) (7,9,1) (8,9,3) 
(1,1,0) (1,2,0) (2,2,2) (3,2,2) (4,2,2) (4,3,1) (4,4,1) (5,4,3) (5,5,2) (6,5,3) (6,6,2) (7,6,1) (7,7,1) (7,8,1) (8,8,3) (8,9,1) 
(1,1,0) (1,2,0) (2,2,1) (2,3,0) (3,3,2) (4,3,2) (4,4,1) (4,5,1) (5,5,3) (5,6,2) (6,6,2) (7,6,2) (7,7,1) (7,8,1) (8,8,3) (8,9,1) 
(1,1,0) (1,2,0) (2,2,1) (2,3,0) (3,3,1) (3,4,0) (4,4,1) (4,5,1) (5,5,3) (5,6,2) (6,6,2) (7,6,2) (7,7,1) (7,8,1) (8,8,3) (8,9,1) 
(1,1,0) (1,2,0) (2,2,0) (2,3,0) (3,3,2) (4,3,2) (4,4,1) (4,5,1) (5,5,3) (5,6,2) (6,6,2) (7,6,2) (7,7,1) (7,8,1) (8,8,3) (8,9,1) 
(1,1,0) (2,1,2) (3,1,2) (4,1,2) (4,2,1) (4,3,1) (4,4,1) (4,5,1) (5,5,3) (5,6,2) (6,6,2) (7,6,2) (7,7,1) (7,8,1) (8,8,3) (8,9,1) 
(1,1,0) (2,1,1) (2,2,0) (3,2,2) (4,2,2) (4,3,1) (4,4,1) (4,5,1) (5,5,3) (5,6,2) (6,6,2) (7,6,2) (7,7,1) (7,8,1) (8,8,3) (8,9,1) 
(1,1,0) (2,1,1) (2,2,0) (3,2,1) (3,3,0) (4,3,2) (5,3,3) (5,4,2) (6,4,3) (6,5,2) (7,5,3) (7,6,2) (7,7,1) (7,8,1) (8,8,3) (8,9,1) 
(1,1,0) (2,1,1) (2,2,0) (3,2,1) (3,3,0) (4,3,1) (4,4,0) (5,4,3) (5,5,2) (6,5,3) (6,6,2) (7,6,2) (7,7,1) (7,8,1) (8,8,3) (8,9,1) 
(1,1,0) (2,1,1) (2,2,0) (3,2,1) (3,3,0) (4,3,1) (4,4,0) (5,4,1) (5,5,0) (6,5,3) (6,6,2) (7,6,2) (7,7,1) (7,8,1) (8,8,3) (8,9,1) 
(1,1,0) (2,1,1) (2,2,0) (3,2,1) (3,3,0) (4,3,1) (4,4,0) (5,4,1) (5,5,0) (6,5,1) (6,6,0) (7,6,2) (7,7,1) (7,8,1) (8,8,3) (8,9,1) 
(1,1,0) (2,1,1) (2,2,0) (3,2,1) (3,3,0) (4,3,1) (4,4,0) (5,4,1) (5,5,0) (6,5,1) (6,6,0) (7,6,1) (7,7,0) (8,7,3) (8,8,0) (8,9,1) 
No path found!
0 1 1 1 1 1 0 0 0 
1 1 1 1 1 1 0 1 0 
0 1 1 1 0 1 0 0 0 
0 0 0 1 0 1 1 1 0 
1 1 0 0 0 0 1 0 0 
1 0 0 1 1 0 1 0 0 
1 1 1 1 0 0 0 1 0 
0 0 0 1 1 1 1 1 0 

其中第一行是从入口到出口的通路，后面的每一行是一条从入口到出口的路径。最后一行是输出迷宫及其到道路。其中0表示通路，1表示障碍。