题解 | #迷宫问题#

import java.util.Scanner;
import java.util.concurrent.ArrayBlockingQueue;

// 本题可以去B站刷一遍：广度优先算法BFS
// 重点是：每一次都是操作队列里的节点，每个节点对应4中可能
// 注意边界判断
// 不才：从头开始理解BFS，搞了3+个小时了，人都傻了
public class Main {
    public static ArrayBlockingQueue<Point> queue;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int a = in.nextInt();
        int b = in.nextInt();
        int[][] arr = new int[a][b];
        int[][] mackArr = new int[a][b];
        queue = new ArrayBlockingQueue<>(a * b);
        for (int i = 0; i < a; i++) {
            for (int j = 0; j < b; j++) {
                arr[i][j] = in.nextInt();
                mackArr[i][j] = 0;
            }
        }
        mackArr[0][0] = 1;
        queue.add(new Point(0, 0, 1, "(0,0)"));
        new Main().BFS(arr, mackArr, a, b);
    }
   
    public void BFS(int[][] arr, int[][] mackArr, int a, int b) {
        Point old = queue.poll();
        if (old == null) {
            return;
        }
        int x = old.getX();
        int y = old.getY();
        if (x == a - 1 && y == b - 1) {
            String[] s = old.getPath().split(" ");
            for (int i = 0; i < s.length; i++) {
                System.out.println(s[i]);
            }
        } else {
            int step = old.getStep() + 1;
            if (x + 1 < a && arr[x + 1][y] == 0 && mackArr[x + 1][y] == 0) {
                Point point = new Point(x + 1, y, step);
                point.setPath(old.path);
                queue.add(point);
                mackArr[x + 1][y] = 1;
            }
            if (y + 1 < b && arr[x][y + 1] == 0 && mackArr[x][y + 1] == 0) {
                Point point = new Point(x, y + 1, step);
                point.setPath(old.path);
                queue.add(point);
                mackArr[x][y + 1] = 1;
            }
            if (x - 1 >= 0 && arr[x - 1][y] == 0 && mackArr[x - 1][y] == 0) {
                Point point = new Point(x - 1, y, step);
                point.setPath(old.path);
                queue.add(point);
                mackArr[x - 1][y] = 1;
            }
            if (y - 1 >= 0 && arr[x][y - 1] == 0 && mackArr[x][y - 1] == 0) {
                Point point = new Point(x, y - 1, step);
                point.setPath(old.path);
                queue.add(point);
                mackArr[x][y - 1] = 1;
            }
            BFS(arr, mackArr, a, b);
        }
    }
    static class Point {
        private int x;
        private int y;
        private int step;//最短路径
        private String path;////回溯路径，通过动态规划赋值

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

        public Point(int x, int y, int step, String path) {
            this.x = x;
            this.y = y;
            this.step = step;
            this.path = path;
        }
        
        public int getX() {
            return x;
        }

        public void setX(int x) {
            this.x = x;
        }

        public int getY() {
            return y;
        }

        public void setY(int y) {
            this.y = y;
        }

        public int getStep() {
            return step;
        }

        public void setStep(int step) {
            this.step = step;
        }

        public String getPath() {
            return path;
        }
		// 这里需要注意，重写计算全路径
        public void setPath(String oldPath) {
            this.path = oldPath + " (" + x + "," + y + ")";;
        }
    }
}