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

首先，我们需要定义一个栈类型的链表实现：

public class Node {
    int x, y, dir;
    Node next;

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

public class Stack {
    Node top;

    public boolean isEmpty() {
        return top == null;
    }

    public void push(int x, int y, int dir) {
        top = new Node(x, y, dir, top);
    }

    public Node pop() {
        Node n = top;
        top = top.next;
        return n;
    }
}

接下来，我们编写一个非递归程序解决迷宫问题：

public class MazeSolver {
    private int[][] maze;
    private int[][] visited;
    private int m, n;
    private int startX, startY, endX, endY;

    public MazeSolver(int[][] maze, int startX, int startY, int endX, int endY) {
        this.maze = maze;
        this.startX = startX;
        this.startY = startY;
        this.endX = endX;
        this.endY = endY;
        this.m = maze.length;
        this.n = maze[0].length;
        this.visited = new int[m][n];
    }

    public void solve() {
        Stack stack = new Stack();
        stack.push(startX, startY, -1);

        while (!stack.isEmpty()) {
            Node node = stack.pop();
            int x = node.x, y = node.y, dir = node.dir;

            if (x == endX && y == endY) {
                printPath(stack);
                return;
            }

            for (int i = dir + 1; i < 4; i++) {
                int nx = x, ny = y;
                switch (i) {
                    case 0:
                        nx--;
                        break;
                    case 1:
                        ny++;
                        break;
                    case 2:
                        nx++;
                        break;
                    case 3:
                        ny--;
                        break;
                }
                if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
                if (maze[nx][ny] == 1 || visited[nx][ny] != 0) continue;
                visited[nx][ny] = 1;
                stack.push(nx, ny, i - 1);
            }
        }

        System.out.println("No solution found!");
    }

    private void printPath(Stack stack) {
        Stack reverseStack = new Stack();
        while (!stack.isEmpty()) {
            reverseStack.push(stack.pop().x, stack.pop().y, 0);
        }

        while (!reverseStack.isEmpty()) {
            Node node = reverseStack.pop();
            System.out.printf("(%d, %d, %d) ", node.x + 1, node.y + 1, node.dir + 1);
        }
        System.out.println();
    }
}

其中，`maze`表示迷宫，`startX`和`startY`表示入口坐标，`endX`和`endY`表示出口坐标。`visited`数组用于记录每个位置是否已经访问过。

我们还可以编写一个递归程序来求解迷宫中所有可能的道路：

public class MazeSolverAllPaths {
    private int[][] maze;
    private int[][] visited;
    private int m, n;
    private int startX, startY, endX, endY;

    public MazeSolverAllPaths(int[][] maze, int startX, int startY, int endX, int endY) {
        this.maze = maze;
        this.startX = startX;
        this.startY = startY;
        this.endX = endX;
        this.endY = endY;
        this.m = maze.length;
        this.n = maze[0].length;
        this.visited = new int[m][n];
    }

    public void solve() {
        Stack stack = new Stack();
        stack.push(startX, startY, -1);

        solveHelper(stack);
    }

    private void solveHelper(Stack stack) {
        if (stack.isEmpty()) return;

        Node node = stack.pop();
        int x = node.x, y = node.y, dir = node.dir;

        if (x == endX && y == endY) {
            printPath(stack);
            return;
        }

        for (int i = dir + 1; i < 4; i++) {
            int nx = x, ny = y;
            switch (i) {
                case 0:
                    nx--;
                    break;
                case 1:
                    ny++;
                    break;
                case 2:
                    nx++;
                    break;
                case 3:
                    ny--;
                    break;
            }
            if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
            if (maze[nx][ny] == 1 || visited[nx][ny] != 0) continue;
            visited[nx][ny] = 1;
            stack.push(nx, ny, i - 1);
            solveHelper(stack);
            visited[nx][ny] = 0;
            stack.pop();
        }
    }

    private void printPath(Stack stack) {
        Stack reverseStack = new Stack();
        while (!stack.isEmpty()) {
            reverseStack.push(stack.pop().x, stack.pop().y, 0);
        }

        while (!reverseStack.isEmpty()) {
            Node node = reverseStack.pop();
            System.out.printf("(%d, %d, %d) ", node.x + 1, node.y + 1, node.dir + 1);
        }
        System.out.println();
    }
}

与非递归程序相比，递归程序只是在`solveHelper`方法中增加了递归调用。

注意，这两个程序都假设迷宫有解。如果迷宫没有解，程序会进入死循环或抛出异常。