3648. 覆盖网格的最少传感器数量

Medium

题目描述

给定一个 n × m 的网格和一个整数 k。

放置在单元格 (r, c) 的传感器可以覆盖所有与 (r, c) 的切比雪夫距离不超过 k 的单元格。

两个单元格 (r1, c1) 和 (r2, c2) 之间的切比雪夫距离是 max(|r1 - r2|, |c1 - c2|)。

你的任务是返回覆盖网格中每个单元格所需的最少传感器数量。

示例 1：

输入：n = 5, m = 5, k = 1

输出：4

解释：

在位置 (0, 3)、(1, 0)、(3, 3) 和 (4, 1) 放置传感器确保网格中的每个单元格都被覆盖。因此，答案是 4。

示例 2：

输入：n = 2, m = 2, k = 2

输出：1

解释：

当 k = 2 时，单个传感器可以覆盖整个 2 × 2 网格，无论其位置如何。因此，答案是 1。

约束条件：

• 1 <= n <= 10³
• 1 <= m <= 10³
• 0 <= k <= 10³

提示：

• 设 s = 2*k + 1，表示每个传感器覆盖的边长。
• 最小数量是 ceil(n / s) * ceil(m / s)。

解题思路

解题思路

这是一个几何覆盖问题，关键在于理解切比雪夫距离和传感器的覆盖范围。

核心观察：

1. 切比雪夫距离 max(|r1-r2|, |c1-c2|) ≤ k 意味着传感器覆盖的是一个正方形区域
2. 传感器覆盖的正方形边长为 2*k+1（中心点加上各方向k个单位）
3. 要用最少的传感器覆盖整个网格，应该让传感器覆盖区域无重叠且无遗漏

数学分析：

• 每个传感器覆盖 (2*k+1) × (2*k+1) 的正方形区域
• 在行方向上需要 ⌈n/(2*k+1)⌉ 个传感器
• 在列方向上需要 ⌈m/(2*k+1)⌉ 个传感器
• 总的传感器数量为两个方向的乘积

这个解法是最优的，因为：

1. 每个传感器都能发挥最大覆盖效果
2. 没有冗余覆盖
3. 保证了完全覆盖

时间复杂度为 O(1)，空间复杂度为 O(1)，是非常高效的数学解法。

代码实现

class Solution {
public:
    int minSensors(int n, int m, int k) {
        int s = 2 * k + 1;
        return ((n + s - 1) / s) * ((m + s - 1) / m);
    }
};

class Solution:
    def minSensors(self, n: int, m: int, k: int) -> int:
        s = 2 * k + 1
        return ((n + s - 1) // s) * ((m + s - 1) // s)

public class Solution {
    public int MinSensors(int n, int m, int k) {
        int s = 2 * k + 1;
        return ((n + s - 1) / s) * ((m + s - 1) / s);
    }
}

var minSensors = function(n, m, k) {
    const s = 2 * k + 1;
    return Math.ceil(n / s) * Math.ceil(m / s);
};

复杂度分析