题解 | 迷宫问题

import java.util.ArrayList;
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            // int a = in.nextInt();
            // int b = in.nextInt();
            // System.out.println(a + b);
            int h = in.nextInt();
            int w = in.nextInt();
            int[][] arr = new int[h][w];
            for (int i=0;i<h;i++) {
                for (int j=0;j<w;j++) {
                    arr[i][j] = in.nextInt();
                }
            }

            ArrayList<Point> road = new ArrayList<>();
            walk(arr, 0, 0, road);

            for (int i=0;i<road.size();i++) {
                System.out.println("(" + road.get(i).x + "," + road.get(i).y + ")");
            }
        }
    }

    private static boolean walk(int[][] arr, int x, int y, ArrayList<Point> road) {
        // 1. 插入新节点
        road.add(new Point(x,y));
        arr[x][y] = 1;

        // 2. 判断结束条件
        if (x == arr.length-1 && y == arr[0].length-1) {
            return true;
        }

        // 3. 尝试所有可能的下一步节点
        // 3.1. 右
        if (y+1 < arr[0].length && arr[x][y+1] == 0) {
            if (walk(arr, x, y+1, road)) {
                return true;
            }
        }
        
        // 3.2. 下
        if (x+1 < arr.length && arr[x+1][y] == 0) {
            if (walk(arr, x+1, y, road)) {
                return true;
            }
        }

        // 3.3. 左
        if (y-1 >= 0 && arr[x][y-1] == 0) {
            if (walk(arr, x, y-1, road)) {
                return true;
            }
        }

        // 3.4. 上 
        if (x-1 >= 0 && arr[x-1][y] == 0) {
            if (walk(arr, x-1, y, road)) {
                return true;
            }
        }

        // 4. 回溯
        road.remove(road.size()-1);
        arr[x][y] = 0;
        return false;
    }
}

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