2026-01-16：覆盖网格的最少传感器数目。用go语言，给定一个 n × m 的格子棋盘和一个非负整数 k。

把传感器放在格子 (r, c) 上时，它能覆盖所有与该格子在“切比雪夫距离”上不超过 k 的格子。

这里的切比雪夫距离可用更直观的方式理解：两格在行号之差和列号之差中的较大值；等价地，传感器能覆盖以 (r, c) 为中心、边长为 2k+1 的正方形区域内的所有格子。

现在要求找出覆盖整个 n × m 棋盘所需的最少传感器数量（即用尽可能少的中心点，使所有格子都被至少一个传感器覆盖）。

1 <= n <= 1000。

1 <= m <= 1000。

0 <= k <= 1000。

输入: n = 5, m = 5, k = 1。

输出: 4。

解释:

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

题目来自力扣3648。

🔢 解决步骤详解

1. 确定单个传感器的覆盖范围
   每个传感器放置在某个格子 (r, c) 上，其覆盖范围由切比雪夫距离 k 定义。这意味着传感器能覆盖所有行号在 [r-k, r+k] 且列号在 [c-k, c+k] 范围内的格子。直观上，每个传感器可以覆盖一个以自身为中心、边长为 2k + 1 的正方形区域。例如，当 k=1 时，传感器覆盖一个3x3的区域。

2. 将二维覆盖问题分解为一维问题
   覆盖整个 n × m 的网格，可以转化为两个独立的一维问题：

   • 需要多少条水平带（由传感器的行覆盖范围构成）才能完全覆盖所有 n 行？
   • 需要多少条垂直带（由传感器的列覆盖范围构成）才能完全覆盖所有 m 列？
     由于传感器的覆盖区域是正方形，这两个问题是对称的。最终所需传感器的总数，就是水平带数量和垂直带数量的乘积。

3. 计算每维所需的“带”数
   对于每一维（例如行方向），一条“带”的宽度（即覆盖范围）是 size = 2k + 1。要覆盖长度为 L（对于行，L = n；对于列，L = m）的维度，所需的最少“带”数可以通过一个简单的公式计算：(L - 1) / size + 1。

   • (L - 1) / size 计算的是 size 的完整倍数覆盖了多少长度。
   • 如果 L 不能被 size 整除，(L - 1) / size 的整数除法会截断小数部分，此时 +1 就是为了覆盖剩余的长度。如果正好整除，(L - 1) / size + 1 的结果也等于 L / size。
   • 这个公式巧妙地处理了所有情况，避免了使用条件判断。

4. 计算传感器总数
   将上述计算应用于行和列：

   • 行方向所需带数：rows = (n - 1) / (2k + 1) + 1
   • 列方向所需带数：cols = (m - 1) / (2k + 1) + 1
     最终结果就是这两个数的乘积：result = rows * cols。这相当于在行方向上的每个放置点，都需要在列方向上放置相应数量的传感器，形成一个均匀的网格布局，确保没有覆盖空隙。

💻 复杂度分析

• 时间复杂度：O(1)
  整个算法只包含固定次数的基本算术运算（加法、乘法和除法），与网格的规模 n 和 m 的大小无关。因此，时间复杂度是常数级别。

• 空间复杂度：O(1)
  算法仅使用了固定数量的整数变量（size, rows, cols, result）来存储中间结果和最终结果，没有使用任何与输入规模相关的额外数据结构。因此，空间复杂度也是常数级别。

💎 总结

该算法通过利用传感器覆盖范围的规则性，将二维覆盖问题高效地简化为两个一维覆盖问题。通过简洁的整数运算直接得出最优解，实现了在常数时间和常数空间内解决问题，非常高效。

Go完整代码如下：

package main

import (
	"fmt"
)

func minSensors(n, m, k int) int {
	size := k*2 + 1
	return ((n-1)/size + 1) * ((m-1)/size + 1)
}

func main() {
	n := 5
	m := 5
	k := 1
	result := minSensors(n, m, k)
	fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

def min_sensors(n: int, m: int, k: int) -> int:
    """
    计算在n×m网格中放置传感器的最小数量
    
    参数:
        n: 网格的行数
        m: 网格的列数  
        k: 传感器的覆盖半径（曼哈顿距离）
    
    返回:
        需要的最小传感器数量
    """
    size = k * 2 + 1  # 每个传感器覆盖的区域大小
    return ((n - 1) // size + 1) * ((m - 1) // size + 1)

def main():
    n = 5
    m = 5
    k = 1
    result = min_sensors(n, m, k)
    print(result)

if __name__ == "__main__":
    main()

C++完整代码如下：

#include <iostream>

/**
 * 计算在n×m网格中放置传感器的最小数量
 *
 * @param n 网格的行数
 * @param m 网格的列数
 * @param k 传感器的覆盖半径（曼哈顿距离）
 * @return 需要的最小传感器数量
 */
int minSensors(int n, int m, int k) {
    int size = k * 2 + 1;  // 每个传感器覆盖的区域大小
    return ((n - 1) / size + 1) * ((m - 1) / size + 1);
}

int main() {
    int n = 5;
    int m = 5;
    int k = 1;
    int result = minSensors(n, m, k);
    std::cout << result << std::endl;
    return 0;
}