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

public class Maze {
    private int[][] maze; // 迷宫矩阵
    private LinkedList<Pos> path; // 路径栈
    private Pos start; // 起点
    private Pos end; // 终点

    public Maze(int[][] maze, Pos start, Pos end) {
        this.maze = maze;
        this.start = start;
        this.end = end;
        path = new LinkedList<>();
    }

    public void solve() {
        path.push(start);
        while (!path.isEmpty()) {
            Pos curPos = path.peek();
            if (curPos.equals(end)) { // 到达终点，输出路径
                for (Pos pos : path) {
                    System.out.print("(" + pos.x + ", " + pos.y + ") ");
                }
                System.out.println();
                return;
            }
            // 尝试向右走
            if (curPos.y + 1 < maze[0].length && maze[curPos.x][curPos.y + 1] == 0) {
                path.push(new Pos(curPos.x, curPos.y + 1, 1));
                maze[curPos.x][curPos.y + 1] = -1; // 将走过的位置标记为 -1
                continue;
            }
            // 尝试向下走
            if (curPos.x + 1 < maze.length && maze[curPos.x + 1][curPos.y] == 0) {
                path.push(new Pos(curPos.x + 1, curPos.y, 2));
                maze[curPos.x + 1][curPos.y] = -1;
                continue;
            }
            // 尝试向左走
            if (curPos.y - 1 >= 0 && maze[curPos.x][curPos.y - 1] == 0) {
                path.push(new Pos(curPos.x, curPos.y - 1, 3));
                maze[curPos.x][curPos.y - 1] = -1;
                continue;
            }
            // 尝试向上走
            if (curPos.x - 1 >= 0 && maze[curPos.x - 1][curPos.y] == 0) {
                path.push(new Pos(curPos.x - 1, curPos.y, 4));
                maze[curPos.x - 1][curPos.y] = -1;
                continue;
            }
            // 四个方向都走不通，回溯
            path.pop();
        }
        System.out.println("No solution.");
    }

    private static class Pos {
        int x;
        int y;
        int d; // 方向，1-右，2-下，3-左，4-上

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

        public boolean equals(Pos p) {
            return x == p.x && y == p.y;
        }
    }

    public static void main(String[] args) {
        int[][] maze = {
                {0, 0, 1, 0, 0, 0},
                {0, 0, 1, 0, 1, 0},
                {0, 0, 0, 0, 1, 0},
                {1, 1, 1, 0, 0, 0},
                {0, 0, 0, 1, 1, 0},
                {0, 0, 0, 0, 0, 0}
        };
        Maze m = new Maze(maze, new Pos(0, 0, 0), new Pos(5, 5, 0));
        m.solve();
    }
}

2. 递归解法

import java.util.ArrayList;

public class MazeAllPaths {
    private int[][] maze; // 迷宫矩阵
    private ArrayList<Pos> path; // 路径
    private ArrayList<ArrayList<Pos>> paths; // 所有路径
    private Pos start; // 起点
    private Pos end; // 终点

    public MazeAllPaths(int[][] maze, Pos start, Pos end) {
        this.maze = maze;
        this.start = start;
        this.end = end;
        path = new ArrayList<>();
        paths = new ArrayList<>();
    }

    public void solve() {
        path.add(start);
        dfs(start);
        if (paths.isEmpty()) {
            System.out.println("No solution.");
        } else {
            for (ArrayList<Pos> p : paths) {
                for (Pos pos : p) {
                    System.out.print("(" + pos.x + ", " + pos.y + ") ");
                }
                System.out.println();
            }
        }
    }

    private void dfs(Pos curPos) {
        if (curPos.equals(end)) { // 到达终点，将路径加入结果集
            paths.add(new ArrayList<>(path));
            return;
        }
        // 尝试向右走
        if (curPos.y + 1 < maze[0].length && maze[curPos.x][curPos.y + 1] == 0) {
            path.add(new Pos(curPos.x, curPos.y + 1));
            maze[curPos.x][curPos.y + 1] = -1;
            dfs(new Pos(curPos.x, curPos.y + 1));
            maze[curPos.x][curPos.y + 1] = 0; // 回溯
            path.remove(path.size() - 1);
        }
        // 尝试向下走
        if (curPos.x + 1 < maze.length && maze[curPos.x + 1][curPos.y] == 0) {
            path.add(new Pos(curPos.x + 1, curPos.y));
            maze[curPos.x + 1][curPos.y] = -1;
            dfs(new Pos(curPos.x + 1, curPos.y));
            maze[curPos.x + 1][curPos.y] = 0;
            path.remove(path.size() - 1);
        }
        // 尝试向左走
        if (curPos.y - 1 >= 0 && maze[curPos.x][curPos.y - 1] == 0) {
            path.add(new Pos(curPos.x, curPos.y - 1));
            maze[curPos.x][curPos.y - 1] = -1;
            dfs(new Pos(curPos.x, curPos.y - 1));
            maze[curPos.x][curPos.y - 1] = 0;
            path.remove(path.size() - 1);
        }
        // 尝试向上走
        if (curPos.x - 1 >= 0 && maze[curPos.x - 1][curPos.y] == 0) {
            path.add(new Pos(curPos.x - 1, curPos.y));
            maze[curPos.x - 1][curPos.y] = -1;
            dfs(new Pos(curPos.x - 1, curPos.y));
            maze[curPos.x - 1][curPos.y] = 0;
            path.remove(path.size() - 1);
        }
    }

    private static class Pos {
        int x;
        int y;

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

        public boolean equals(Pos p) {
            return x == p.x && y == p.y;
        }
    }

    public static void main(String[] args) {
        int[][] maze = {
                {0, 0, 1, 0, 0, 0},
                {0, 0, 1, 0, 1, 0},
                {0, 0, 0, 0, 1, 0},
                {1, 1, 1, 0, 0, 0},
                {0, 0, 0, 1, 1, 0},
                {0, 0, 0, 0, 0, 0}
        };
        MazeAllPaths m = new MazeAllPaths(maze, new Pos(0, 0), new Pos(5, 5));
        m.solve();
    }
}