LeetCode 剑指 Offer 13. 机器人的运动范围

Categories:

题目描述
思路分析
1. 解法一：BFS + 访问标记（推荐）
相似题目

题目描述

✅ 剑指 Offer 13. 机器人的运动范围

思路分析

解法一：BFS + 访问标记（推荐）

核心思路：

从 (0, 0) 出发，用 BFS 逐步扩展可达格子。

当坐标数位和大于 k 时不可进入，使用 visited 避免重复。

因为坐标非负，从任意可达点继续向右/向下扩展即可覆盖所有可达位置。

复杂度分析：

时间复杂度：O(m * n)，其中 m、n 分别表示网格的行列数。

空间复杂度：O(m * n)，其中 m、n 分别表示网格的行列数。

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public int movingCount(int m, int n, int k) {
        if (m <= 0 || n <= 0 || k < 0) {
            return 0;
        }

        boolean[][] visited = new boolean[m][n];
        Deque<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[] {0, 0});

        int count = 0;
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int x = cur[0];
            int y = cur[1];

            if (x < 0 || x >= m || y < 0 || y >= n) {
                continue;
            }
            if (visited[x][y]) {
                continue;
            }
            if (digitSum(x) + digitSum(y) > k) {
                continue;
            }

            visited[x][y] = true;
            count++;

            // 只需向右和向下扩展
            queue.offer(new int[] {x + 1, y});
            queue.offer(new int[] {x, y + 1});
        }

        return count;
    }

    private int digitSum(int x) {
        int sum = 0;
        while (x > 0) {
            sum += x % 10;
            x /= 10;
        }
        return sum;
    }
}

func movingCount(m int, n int, k int) int {
	if m <= 0 || n <= 0 || k < 0 {
		return 0
	}

	visited := make([][]bool, m)
	for i := range visited {
		visited[i] = make([]bool, n)
	}

	queue := make([][2]int, 0)
	queue = append(queue, [2]int{0, 0})
	count := 0

	for len(queue) > 0 {
		cur := queue[0]
		queue = queue[1:]
		x, y := cur[0], cur[1]

		if x < 0 || x >= m || y < 0 || y >= n {
			continue
		}
		if visited[x][y] {
			continue
		}
		if digitSum(x)+digitSum(y) > k {
			continue
		}

		visited[x][y] = true
		count++

		// 只需向右和向下扩展
		queue = append(queue, [2]int{x + 1, y})
		queue = append(queue, [2]int{x, y + 1})
	}

	return count
}

func digitSum(x int) int {
	sum := 0
	for x > 0 {
		sum += x % 10
		x /= 10
	}
	return sum
}

相似题目

题目	难度	考察点
200. 岛屿数量	中等	DFS/BFS
695. 岛屿的最大面积	中等	DFS/BFS
733. 图像渲染	简单	DFS/BFS
1091. 二进制矩阵中的最短路径	中等	BFS
130. 被围绕的区域	中等	DFS/BFS

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/41608047