题解 | #迷宫问题#

深度优先搜索 ，向四个方向下一步搜索

import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static List<int[]> result = null;
    public static List<int[]> temp = new ArrayList<int[]>();
    public static boolean flag = false;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int line = in.nextInt();
            int lie = in.nextInt();
            int[][] drop = new int[line][lie];
            for (int i = 0; i < line; i++) {
                for (int j = 0; j < lie; j++) {
                    drop[i][j] = in.nextInt();
                }
            }
            dfs(drop, 0, 0, 0);
            for (int[] ll : result) {
                System.out.println("(" + ll[0] + "," + ll[1] + ")");
            }
        }
    }
    public static void dfs(int[][] drop, int count, int line, int lie) {
        if (line == drop.length - 1 && lie == drop[0].length - 1) {
            flag = true;
            temp.add(new int[] {line, lie});
            if (count < temp.size() ||  temp.size() == 0) {
                result = new ArrayList<int[]>(temp);
            }
            return;
        }
        temp.add(new int[] {line, lie});
        drop[line][lie] = 1;
        if (line - 1 >= 0 && drop[line - 1][lie] == 0) {
            dfs(drop, count + 1, line - 1, lie);
        }
        if (lie - 1 >= 0 && drop[line][lie - 1] == 0) {
            dfs(drop, count + 1, line, lie - 1);
        }
        if ( line + 1 < drop.length && drop[line + 1][lie] == 0) {
            dfs(drop, count + 1, line + 1, lie);
        }
        if ( lie + 1 < drop[0].length && drop[line][lie + 1] == 0) {
            dfs(drop, count + 1, line, lie + 1);
        }
        temp.remove(temp.size() - 1);
        drop[line][lie] = 0;
    }
}