题解 | 迷宫问题

import java.util.LinkedList;
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static LinkedList<Integer>stack = new LinkedList<>();
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            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();
                }
            }
            boolean[][]visit = new boolean[h][w];
            dfs(0, 0, visit, arr);
            while (!stack.isEmpty()) {
                int index = stack.pop();

                System.out.print('(');
                System.out.print(index / w);
                System.out.print(',');
                System.out.print(index % w);
                System.out.println(')');

            }

        }

    }
    public static boolean dfs(int i, int j, boolean[][]visit, int[][]arr) {
        visit[i][j] = true;
        if (i == arr.length - 1 && j == arr[0].length - 1) {
            stack.push(i * arr[0].length + j);
            return true;
        }

        if (i - 1 >= 0 && !visit[i - 1][j] && arr[i - 1][j] == 0) {

            if (dfs(i - 1, j, visit, arr)) {
                stack.push(i * arr[0].length + j);
                return true;

            }
        }
        if (i + 1 < arr.length && !visit[i + 1][j] && arr[i + 1][j] == 0) {
            if (dfs(i + 1, j, visit, arr)) {
                stack.push(i * arr[0].length + j);
                return true;
            }
        }
        if (j - 1 >= 0 && !visit[i][j - 1] && arr[i][j - 1] == 0) {
            if (dfs(i, j - 1, visit, arr)) {
                stack.push(i * arr[0].length + j);
                return true;
            }
        }
        if (j + 1 < arr[0].length && !visit[i][j + 1] && arr[i][j + 1] == 0) {
            if (dfs(i, j + 1, visit, arr)) {
                stack.push(i * arr[0].length + j);
                return true;

            }
        }
        visit[i][j] = false;
        return false;

    }
}