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

首先，我们可以使用一个二维数组来表示迷宫，其中0表示通路，1表示障碍。假设起点为(0,0)，出口为(m-1,n-1)。

（1）非递归算法

我们可以使用栈来记录当前的位置和方向。从起点开始，将其入栈，并且标记为已经访问过。然后不断进行如下操作：

1. 取出栈顶元素，记录当前位置和方向。
2. 如果当前位置是终点，则输出路径并结束程序。
3. 否则，依次尝试向上、右、下、左四个方向移动，如果该方向是通路并且没有访问过，则将新的位置和方向入栈，并且标记为已经访问过。
4. 如果四个方向都不能移动，则将该位置出栈。

代码如下：

public class MazeSolver {
    private static final int[][] DIRECTIONS = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // 上右下左四个方向

    public static List<int[]> solveMaze(int[][] maze) {
        int m = maze.length;
        int n = maze[0].length;
        boolean[][] visited = new boolean[m][n];
        Stack<int[]> stack = new Stack<>(); // 存储当前位置和方向
        stack.push(new int[]{0, 0, 0}); // 起点入栈
        visited[0][0] = true;

        while (!stack.empty()) {
            int[] curr = stack.pop();
            int i = curr[0];
            int j = curr[1];
            int d = curr[2];
            if (i == m - 1 && j == n - 1) { // 到达终点
                List<int[]> path = new ArrayList<>();
                Stack<int[]> tmpStack = new Stack<>(); // 用于反转路径
                tmpStack.push(curr);
                while (!stack.empty()) {
                    tmpStack.push(stack.pop()); // 将路径上的元素全部倒入tmpStack中
                }
                while (!tmpStack.empty()) {
                    path.add(tmpStack.pop()); // 将路径上的元素按顺序放入path中
                }
                return path;
            }
            for (int k = 0; k < 4; k++) { // 尝试四个方向
                int ni = i + DIRECTIONS[k][0];
                int nj = j + DIRECTIONS[k][1];
                if (ni >= 0 && ni < m && nj >= 0 && nj < n && maze[ni][nj] == 0 && !visited[ni][nj]) { // 可以移动
                    stack.push(new int[]{ni, nj, k});
                    visited[ni][nj] = true;
                }
            }
        }
        return null; // 没有找到路径
    }
}

（2）递归算法

递归算法可以分为两步：

1. 从起点开始，尝试四个方向移动，如果该方向是通路并且没有访问过，则递归地继续向该方向移动。
2. 如果四个方向都不能移动，则回溯到上一个位置，尝试另外的方向。

代码如下：

public class MazeSolver {
    private static final int[][] DIRECTIONS = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // 上右下左四个方向

    public static List<List<int[]>> solveMaze(int[][] maze) {
        int m = maze.length;
        int n = maze[0].length;
        boolean[][] visited = new boolean[m][n];
        List<List<int[]>> paths = new ArrayList<>();
        List<int[]> path = new ArrayList<>();
        path.add(new int[]{0, 0});
        solveMazeHelper(maze, 0, 0, visited, path, paths);
        return paths;
    }

    private static void solveMazeHelper(int[][] maze, int i, int j, boolean[][] visited, List<int[]> path, List<List<int[]>> paths) {
        if (i == maze.length - 1 && j == maze[0].length - 1) { // 到达终点
            paths.add(new ArrayList<>(path)); // 将路径加入结果列表
            return;
        }
        visited[i][j] = true;
        for (int k = 0; k < 4; k++) { // 尝试四个方向
            int ni = i + DIRECTIONS[k][0];
            int nj = j + DIRECTIONS[k][1];
            if (ni >= 0 && ni < maze.length && nj >= 0 && nj < maze[0].length && maze[ni][nj] == 0 && !visited[ni][nj]) { // 可以移动
                path.add(new int[]{ni, nj});
                solveMazeHelper(maze, ni, nj, visited, path, paths);
                path.remove(path.size() - 1); // 回溯
            }
        }
        visited[i][j] = false;
    }
}