题解 | 迷宫问题

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

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int m = sc.nextInt();
            int n = sc.nextInt();
            int[][] t = new int[m][n];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    t[i][j] = sc.nextInt();
                }
            }
            List<int[]> list = new ArrayList<>();
            int[][] visity = new int[m][n];
            visity[0][0] = 1;
            dfs(t, 0, 0, list, visity);
        }
    }

    static void dfs(int[][] t, int x, int y, List<int[]> list, int[][] visity) {
        //System.out.println("当前位置("+x+","+y+")");
        int m = t.length;
        int n = t[0].length;
        list.add(new int[] {x, y});
        if (x == m - 1 && y == n - 1) {
            for (int i = 0; i < list.size(); i++) {
                System.out.println("(" + list.get(i)[0] + "," + list.get(i)[1] + ")");
            }
            return;
        }
        if (x - 1 >= 0 && visity[x - 1][y] == 0 && t[x - 1][y] == 0) {
            visity[x - 1][y] = 1;
            dfs(t, x - 1, y, list, visity);
            visity[x - 1][y] = 0;
            list.remove(list.size() - 1);
        }
        if (x + 1 < m && visity[x + 1][y] == 0 && t[x + 1][y] == 0) {
            visity[x + 1][y] = 1;
            dfs(t, x + 1, y, list, visity);
            visity[x + 1][y] = 0;
            list.remove(list.size() - 1);
        }
        if (y - 1 >= 0 && visity[x][y - 1] == 0 && t[x][y - 1] == 0) {
            visity[x][y - 1] = 1;
            dfs(t, x, y - 1, list, visity);
            visity[x][y - 1] = 0;
            list.remove(list.size() - 1);
        }
        if (y + 1 < n && visity[x][y + 1] == 0 && t[x][y + 1] == 0) {
            visity[x][y + 1] = 1;
            dfs(t, x, y + 1, list, visity);
            visity[x][y + 1] = 0;
            list.remove(list.size() - 1);
        }
    }
}