题目描述

解题思路

详细解法🔗

DFS

此题和矩阵中的路径解题思路一致，但此题只需要向下和向右递归。

int m, n, k;
boolean[][] visited;
public int movingCount(int m, int n, int k) {
    this.m = m;
    this.n = n;
    this.k = k;
    visited = new boolean[m][n];
    // 从 (0,0) 开始
    return dfs(0, 0, 0, 0);
}
/**
         * dfs深搜
         * 时间复杂度 O(MN)O(MN) ： 最差情况下，机器人遍历矩阵所有单元格，此时时间复杂度为 O(MN)O(MN) 。
         * 空间复杂度 O(MN)O(MN) ： 最差情况下，Set visited 内存储矩阵所有单元格的索引，使用 O(MN)O(MN) 的额外空间。
         *
         * @param i  代表此时的x
         * @param j  代表此时的y
         * @param si 此时x的位和
         * @param sj 此时y的位和
         * @return
         */
    public int dfs(int i, int j, int si, int sj) {
    // 越界或者已经访问过
    if (i >= m || j >= n || k < si + sj || visited[i][j]) return 0;
    visited[i][j] = true;   // 访问过
    return 1 + dfs(i + 1, j, (i + 1) % 10 == 0 ? si - 8 : si + 1, sj) + dfs(i, j + 1, si, (j + 1) % 10 == 0 ? sj - 8 : sj + 1);
}

BFS

BFS思路和DFS思路相差不大，只是BFS将下边和右边的元素入队之后在进行判断。

/**
         * bfs搜索
         *
         * @param m
         * @param n
         * @param k
         * @return
         */
public int movingCount(int m, int n, int k) {
    int res = 0;    // 表示机器人可以走动结果
    Queue<int[]> queue = new LinkedList<>();    // 队列，记录遍历过的数组
    queue.offer(new int[]{0, 0, 0, 0});
    boolean[][] visited = new boolean[m][n]; // 表示是否走过
    while (!queue.isEmpty()) {
        int[] poll = queue.poll();
        int i = poll[0], j = poll[1], si = poll[2], sj = poll[3];
        if (i >= m || j >= n || k < si + sj || visited[i][j]) continue;  // 越界或者相加大于k，或者访问过的，直接跳过
        visited[i][j] = true;
        res++;
        queue.offer(new int[]{i + 1, j, (i + 1) % 10 == 0 ? si - 8 : si + 1, sj}); // 下边元素入栈
        queue.offer(new int[]{i, j + 1, si, (j + 1) % 10 == 0 ? sj - 8 : sj + 1}); // 右边元素入栈
    }
    return res;
}