用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） 编写递归形式的算法，并且使用回溯的方法 求得迷宫中所有可能的道路；

以下是Java语言实现迷宫求解的代码：

1. 非递归算法

import java.util.LinkedList;
import java.util.Stack;

public class MazeSolver {
    private int[][] maze;
    private boolean[][] visited;
    private int n, m;

    public MazeSolver(int[][] maze) {
        this.maze = maze;
        n = maze.length;
        m = maze[0].length;
        visited = new boolean[n][m];
    }

    public LinkedList<int[]> solve(int[] start, int[] end) {
        Stack<int[]> stack = new Stack<>();
        LinkedList<int[]> path = new LinkedList<>();

        int[] cur = start;
        stack.push(cur);

        while (!stack.isEmpty()) {
            cur = stack.pop();
            visited[cur[0]][cur[1]] = true;
            path.add(cur);

            if (cur[0] == end[0] && cur[1] == end[1])
                return path;

            int[][] next = {{cur[0], cur[1] + 1}, {cur[0] + 1, cur[1]}, {cur[0], cur[1] - 1}, {cur[0] - 1, cur[1]}};

            for (int[] n : next) {
                if (n[0] >= 0 && n[0] < n && n[1] >= 0 && n[1] < m && maze[n[0]][n[1]] == 0 && !visited[n[0]][n[1]]) {
                    stack.push(n);
                }
            }
        }

        return null;
    }
}

2. 递归算法

import java.util.LinkedList;

public class MazeSolver {
    private int[][] maze;
    private boolean[][] visited;
    private int n, m;

    public MazeSolver(int[][] maze) {
        this.maze = maze;
        n = maze.length;
        m = maze[0].length;
        visited = new boolean[n][m];
    }

    public LinkedList<int[]> solve(int[] start, int[] end) {
        LinkedList<int[]> path = new LinkedList<>();
        dfs(start[0], start[1], end[0], end[1], path);
        return path;
    }

    private boolean dfs(int x, int y, int ex, int ey, LinkedList<int[]> path) {
        if (x == ex && y == ey) {
            path.add(new int[]{x, y});
            return true;
        }

        visited[x][y] = true;

        int[][] next = {{x, y + 1}, {x + 1, y}, {x, y - 1}, {x - 1, y}};

        for (int[] n : next) {
            if (n[0] >= 0 && n[0] < n && n[1] >= 0 && n[1] < m && maze[n[0]][n[1]] == 0 && !visited[n[0]][n[1]]) {
                if (dfs(n[0], n[1], ex, ey, path)) {
                    path.addFirst(new int[]{x, y});
                    return true;
                }
            }
        }

        return false;
    }
}