题解 | 迷宫问题

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int m = in.nextInt();
        int n = in.nextInt();
        int[][] a = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                a[i][j] = in.nextInt();
            }
        }
        int[][] visited = new int[m][n];
        dfs(a, 0, 0, m, n, visited);
        for (int[] ints : list) {
            System.out.println("(" + ints[0] + "," + ints[1] + ")");
        }
    }

    static ArrayList<int[]> list = new ArrayList<>();

    public static boolean dfs(int[][] a, int x, int y, int m, int n,
                              int[][] visited) {
        if (x < 0 || x >= m || y < 0 || y >= n || a[x][y] == 1 || visited[x][y] == 1) {
            return false;
        }
        list.add(new int[] {x, y});
        if (x == m - 1 && y == n - 1) {
            return true;
        }
        visited[x][y] = 1;
        if (dfs(a, x + 1, y, m, n, visited) || dfs(a, x, y + 1, m, n, visited) ||
                dfs(a, x, y - 1, m, n, visited) || dfs(a
                        , x - 1, y, m, n, visited)) {
            return true;
        } else {
            visited[x][y] = 0;
            list.remove(list.size() - 1);
            return false;
        }

    }
}

#牛客春招刷题训练营#

这题使用dfs,题目只要求一条满足要求的路径就行了，并不需要求所有的路径，所有只要能够达到目的地就可以直接结束搜索过程，这点需要注意，这题有点疑问的是不知道如果转圈的话，会不会也算通过，没去尝试过