题解 | 迷宫问题

import java.util.Scanner;

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

public class Main {
    static List<List<String>> res = new ArrayList<>();
    static List<String> path = new ArrayList<>();
    static int[][] direct = new int[][] {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int h = sc.nextInt();//row
        int w = sc.nextInt();//col
        int[][] grid = new int[h][w];
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                grid[i][j] = sc.nextInt();
            }
        }
        boolean[][] visited = new boolean[h][w];
        path.add("(0,0)");
        dfs(0, 0, grid, visited);
        if (res.size() > 0) {
            for (String string : res.get(0)) {
                System.out.println(string);
            }
        }
    }

    private static void dfs(int i, int j, int[][] grid, boolean[][] visited) {
        if (i == grid.length - 1 && j == grid[0].length - 1) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int k = 0; k < direct.length; k++) {
            int newi = i + direct[k][0];
            int newj = j + direct[k][1];
            //下标越界 跳过
            if (newi < 0 || newj < 0 || newi >= grid.length || newj >= grid[0].length) {
                continue;
            }
            //遇到障碍物 跳过
            if (grid[newi][newj] == 1) {
                continue;
            }
            //访问过了 跳过
            if (visited[newi][newj]) {
                continue;
            }
            visited[newi][newj] = true;
            path.add("(" + newi + "," + newj + ")");
            dfs(newi, newj, grid, visited);
            path.remove(path.size() - 1);
        }
    }
}