题解 | #迷宫问题#

import java.util.LinkedList;
import java.util.List;
import java.util.ArrayList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
        int a = 0;
        int b = 0;
        int[][] maze = null;
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            a = in.nextInt();
            b = in.nextInt();
            maze = new int[a][b];
            for (int i = 0; i < a; i++) {
                for (int j = 0; j < b; j++) {
                    maze[i][j] = in.nextInt();
                }
            }
        }
        Stack<Pos> path = new Stack<Pos>();
        dfs(maze, path, a, b);
    }
    private static void dfs(int[][] maze, Stack<Pos> path, int a, int b) {
        path.push(new Pos(0, 0, null));
        maze[0][0] = 2;// 标记已读
        Pos pos = null;
        while (true) {
            pos = path.pop();
            int r = pos.r;
            int c = pos.c;
            if (r >= a - 1 && c >= b - 1) break;
            else {
                if (r + 1 < a && maze[r + 1][c] == 0) { // go down
                    maze[r + 1][c] = 2;
                    path.push(new Pos(r + 1, c, pos));
                }
                if (c + 1 < b && maze[r][c + 1] == 0) { // go right
                    maze[r][c + 1] = 2;
                    path.push(new Pos(r, c + 1, pos));
                }
                if (r - 1 >= 0 && maze[r - 1][c] == 0) { // go up
                    maze[r - 1][c] = 2;
                    path.push(new Pos(r - 1, c, pos));
                }
                if (c - 1 >= 0 && maze[r][c - 1] == 0) { // go left
                    maze[r][c - 1] = 2;
                    path.push(new Pos(r, c - 1, pos));
                }
            }
        }
        print(pos);
    }

    public static void print(Pos pos) {
        if (pos != null) {
            print(pos.father);
            System.out.println(pos.getString());
        }
    }
}
class Pos {
    int r;
    int c;
    Pos father;
    Pos(int r, int c, Pos value) {
        this.r = r;
        this.c = c;
        this.father = value;
    }
    public String getString() {
        return "(" + r + "," + c + ")";
    }

}

dfs ， depth first search 深度优先遍历。深度理解