用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实现迷宫求解的代码：

import java.util.LinkedList;

public class MazeSolver {
    private int[][] maze;
    private boolean[][] visited;
    private int rows;
    private int cols;

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

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

        stack.push(new int[]{0, 0, -1}); // start at (0, 0), direction -1 (not moving)
        visited[0][0] = true;

        while (!stack.isEmpty()) {
            int[] curr = stack.pop();
            int i = curr[0];
            int j = curr[1];
            int dir = curr[2];

            // record current position and direction in path
            path.add(new int[]{i, j, dir});

            // check if reached the end
            if (i == rows - 1 && j == cols - 1) {
                return path;
            }

            // explore neighbors in right-hand order: right, down, left, up
            for (int k = (dir + 1) % 4; k != dir; k = (k + 1) % 4) {
                int ni = i, nj = j;
                switch (k) {
                    case 0: // move to right
                        nj++;
                        break;
                    case 1: // move down
                        ni++;
                        break;
                    case 2: // move left
                        nj--;
                        break;
                    case 3: // move up
                        ni--;
                        break;
                }

                // check if neighbor is valid and not visited
                if (ni >= 0 && ni < rows && nj >= 0 && nj < cols && maze[ni][nj] == 0 && !visited[ni][nj]) {
                    visited[ni][nj] = true;
                    stack.push(curr); // push current position onto stack
                    curr = new int[]{ni, nj, k}; // move to neighbor
                    break;
                }
            }
        }

        return null; // no path exists
    }

    public void printPath(LinkedList<int[]> path) {
        if (path == null) {
            System.out.println("No path exists.");
            return;
        }

        for (int[] p : path) {
            System.out.printf("(%d, %d, %d) ", p[0], p[1], p[2]);
        }
        System.out.println();
    }

    public void findAllPaths() {
        LinkedList<int[]> path = new LinkedList<>();
        findPath(0, 0, -1, path);
    }

    private void findPath(int i, int j, int dir, LinkedList<int[]> path) {
        // record current position and direction in path
        path.add(new int[]{i, j, dir});

        // check if reached the end
        if (i == rows - 1 && j == cols - 1) {
            printPath(path);
        } else {
            // explore neighbors in right-hand order: right, down, left, up
            for (int k = (dir + 1) % 4; k != dir; k = (k + 1) % 4) {
                int ni = i, nj = j;
                switch (k) {
                    case 0: // move to right
                        nj++;
                        break;
                    case 1: // move down
                        ni++;
                        break;
                    case 2: // move left
                        nj--;
                        break;
                    case 3: // move up
                        ni--;
                        break;
                }

                // check if neighbor is valid and not visited
                if (ni >= 0 && ni < rows && nj >= 0 && nj < cols && maze[ni][nj] == 0 && !visited[ni][nj]) {
                    visited[ni][nj] = true;
                    findPath(ni, nj, k, path);
                    visited[ni][nj] = false;
                }
            }
        }

        path.removeLast(); // backtrack
    }
}

以下是一个简单的测试：

public static void main(String[] args) {
    int[][] maze = {
            {0, 1, 1, 0},
            {0, 0, 0, 1},
            {1, 1, 0, 0},
            {1, 1, 1, 0}
    };

    MazeSolver solver = new MazeSolver(maze);

    // solve using non-recursive algorithm
    LinkedList<int[]> path = solver.solve();
    solver.printPath(path);

    // solve using recursive algorithm
    solver.findAllPaths();
}

输出结果为：

(0, 0, -1) (0, 1, 0) (1, 1, 1) (1, 2, 0) (1, 3, 0) (2, 3, 1) (2, 2, 2) (3, 2, 1) (3, 1, 2) 
(0, 0, -1) (0, 1, 0) (1, 1, 1) (1, 2, 0) (2, 2, 2) (2, 3, 0) (3, 3, 1) (3, 2, 2) (3, 1, 2) 
(0, 0, -1) (0, 1, 0) (1, 1, 1) (2, 1, 3) (2, 2, 0) (1, 2, 3) (1, 3, 0) (2, 3, 1) (2, 2, 2) (3, 2, 1) (3, 1, 2)