题解 | #迷宫问题#

// mark一下

import java.util.*;

public class Main {

    static class City {
        int x;
        int y;
        int val;
        City father;

        public City(int x, int y, int val, City father) {
            this.x = x;
            this.y = y;
            this.val = val;
            this.father = father;
        }

        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 getVal() {
            return val;
        }

        public void setVal(int val) {
            this.val = val;
        }

        public City getFather() {
            return father;
        }

        public void setFather(City father) {
            this.father = father;
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) {
            String s = in.nextLine();
            String[] strings = s.split(" ");
            int n = Integer.parseInt(strings[0]);
            int m = Integer.parseInt(strings[1]);

            int[][] array = new int[n][m];
            for (int i = 0; i < n; i++) {
                String str = in.nextLine();
                String[] strs = str.split(" ");
                for (int j = 0; j < m; j++) {
                    array[i][j] = Integer.parseInt(strs[j]);
                }
            }

            Queue<City> queue = new LinkedList<>();
            City root = new City(0, 0, array[0][0], null);
            array[0][0] = 1;
            queue.offer(root);

            City endFather = new City(-1, -1, -1, null);
            while (!queue.isEmpty()) {
                City cur = queue.poll();
                int curX = cur.getX();
                int curY = cur.getY();
                int curVal = cur.getVal();
                City father = cur.getFather();

                // 下
                int rightX = curX + 1;
                if (rightX < n && array[rightX][curY] == 0) {
                    array[rightX][curY] = 1;
                    queue.offer(new City(rightX, curY, 1, cur));
                    if (rightX == n - 1 && curY == m - 1) {
                        endFather = cur;
                        break;
                    }
                }

                // 右
                int downY = curY + 1;
                if (downY < m && array[curX][downY] == 0) {
                    queue.offer(new City(curX, downY, 1, cur));
                    array[curX][downY] = 1;
                    if (curX == n - 1 && downY == m - 1) {
                        endFather = cur;
                        break;
                    }
                }

                // 上
                int leftX = curX - 1;
                if (leftX >= 0 && array[leftX][curY] == 0) {
                    queue.offer(new City(leftX, curY, 1, cur));
                    array[leftX][curY] = 1;
                    if (leftX == n - 1 && curY == m - 1) {
                        endFather = cur;
                        break;
                    }
                }

                // 左
                int upY = curY - 1;
                if (upY >= 0 && array[curX][upY] == 0) {
                    queue.offer(new City(curX, upY, 1, cur));
                    array[curX][upY] = 1;
                    if (curX == n - 1 && curY == m - 1) {
                        endFather = cur;
                        break;
                    }
                }
            }

            Stack<City> pathCity = new Stack<>();
            while (endFather.getFather() != null) {
                pathCity.push(endFather);
                endFather = endFather.getFather();
            }

            System.out.println("(" + 0 + "," + 0 + ")");
            while (!pathCity.isEmpty()) {
                City curCity = pathCity.pop();
                System.out.println("(" + curCity.getX() + "," + curCity.getY() + ")");
            }
            System.out.println("(" + (n - 1) + "," + (m - 1) + ")");
        }
    }
}