题解 | #迷宫问题#

用了stack

pop()是弹出并删除

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while(in.hasNextInt()) {
            int col_num = in.nextInt();
            int row_num = in.nextInt();
            int[][] maze = new int[col_num][row_num];
            for (int i = 0; i < col_num; i++) {
                for (int j = 0; j < row_num; j++) {
                    maze[i][j] = in.nextInt();
                }
            }

            List<Point> lp = new ArrayList<>();
            lp.add(new Point(0, 0, null));
            int x = 0, y = 0;
            Point p = null;
            while (true) {
                p = lp.remove(lp.size() - 1); //注意这里要remove而不是仅仅get
                //System.out.println(p.toString());
                x = p.x;
                y = p.y;
                if (x == col_num - 1 && y == row_num - 1) {
                    break;
                } else {
                    if (x - 1 >= 0 && maze[x - 1][y] == 0) { //check upper point
                        maze[x - 1][y] = 1;
                        lp.add(new Point(x - 1, y, p));
                    }
                    if (x + 1 < col_num && maze[x + 1][y] == 0) { //check lower point
                        maze[x + 1][y] = 1;
                        lp.add(new Point(x + 1, y, p));
                    }
                    if (y - 1 >= 0 && maze[x][y - 1] == 0) { //check left point
                        maze[x][y - 1] = 1;
                        lp.add(new Point(x, y - 1, p));
                    }
                    if (y + 1 < row_num && maze[x][y + 1] == 0) { //check right point
                        maze[x][y + 1] = 1;
                        lp.add(new Point(x, y + 1, p));
                    }
                }
            }

            Stack<Point> stack = new Stack<>();
            while (p != null) {
                stack.push(p);
                p = p.father;
            }

            while (!stack.isEmpty()) {
                Point temp = stack.pop();
                System.out.println("(" + temp.x + "," + temp.y + ")");
            }
        }
        in.close();
    }
}

class Point{
    int x,y;
    Point father;

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

    @Override
    public String toString() {
        return "Point{" +
                "x=" + x +
                ", y=" + y +
                ", father=" + father +
                '}';
    }
}