题解 | #迷宫问题#

本题使用深度优先搜索，不熟悉深度优先搜索可以看b站视频：https://www.bilibili.com/video/BV1JU4y1p7Ue/

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();

        // 构造迷宫
        Point[][] points = new Point[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (scanner.nextInt() == 1) {
                    points[i][j] = new Point(i, j, true);
                } else {
                    points[i][j] = new Point(i, j, false);
                }
            }
        }

        // 栈，用于储存路径
        Stack<Point> stack = new Stack<>();
        // 最短的路径
        List<Point> min = new ArrayList<>();
        // 初始化为最长的路径
        for (int i = 0; i < n; i++) {
            min.addAll(Arrays.asList(points[i]));
        }
        // 起始点
        stack.push(points[0][0]);
        points[0][0].isVisited = true;
        // 栈为空表示已全部遍历
        while (stack.size() > 0) {
            // 取栈的最外层的点
            Point now = stack.get(stack.size() - 1);
            // 如果遍历到了终点，而且当前路径比之前的路径短，则更新最短路径
            if (now == points[n - 1][m - 1] && stack.size() < min.size()) {
                min = new ArrayList<>(stack);
                // 如果当前路径已经最短，则退出遍历循环
                if (min.size() == n + m -1) {
                    break;
                }
            }
            // 寻找下一个点
            Point next = now.next(points);
            // 如果找不到，则回溯
            if (next == null) {
                stack.pop();
                continue;
            }
            // 下一个点入栈，并设为已访问
            stack.push(next);
            next.isVisited = true;
        }

        // 输出路径
        for (Point point : min) {
            System.out.println(point);
        }
    }
}

class Point {
    private final int i;
    private final int j;
    final boolean isWall;
    boolean isVisited;

    public Point(int i, int j, boolean isWall) {
        this.i = i;
        this.j = j;
        this.isWall = isWall;
    }

    public Point next(Point[][] points) {
        // 向下走
        if (i + 1 < points.length && !points[i + 1][j].isWall && !points[i + 1][j].isVisited) {
            return points[i + 1][j];
        }
        // 向右走
        if (j + 1 < points[0].length && !points[i][j + 1].isWall && !points[i][j + 1].isVisited) {
            return points[i][j + 1];
        }
        // 向上走
        if (i - 1 >= 0 && !points[i - 1][j].isWall && !points[i - 1][j].isVisited) {
            return points[i - 1][j];
        }
        // 向左走
        if (j - 1 >= 0 && !points[i][j - 1].isWall && !points[i][j - 1].isVisited) {
            return points[i][j - 1];
        }
        
        return null;
    }

    @Override
    public String toString() {
        return "(" + this.i + "," + this.j + ")";
    }
}