logoChat01.ai

给你一个 n × m 的网格和一个整数 k。 一个放置在单元格 (r, c) 的传感器可以覆盖所有...

创建于：2025年8月16日

使用 GPT-5 Thinking 回答 Chat01

问题

给你一个 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^3
1 <= m <= 10^3
0 <= k <= 10^3

class Solution {
public int minSensors(int n, int m, int k) {

} 解决这个问题，通过所有例子，并且不能超时
}

思考

Implementing minimal sensors

The task is to implement a Java method minSensors(n,m,k) that calculates the minimum number of Chebyshev squares with a given radius, k, to cover an n x m grid. The coverage is determined by axis-aligned squares, and the formula involves using integer math to avoid overflow. The algorithm should be efficient with a complexity of O(1).

Finalizing algorithm and explanation

I’m preparing a minimal solution in Java to meet the user's requirements. The method should handle the case where k=0, meaning the number of sensors equals n*m. I'll write the method stub in a class and provide the full explanation in Chinese. It will use integer math and be efficient with O(1) complexity. Edge cases won’t be necessary here. Hopefully, the solution is simple enough to pass all examples!

Providing minimal solution

Let's create the Java method minSensors(int n, int m, int k) based on the understanding that it's optimal to tile the grid with squares of size `(2k+1) x (2k+1)

Thought for 9s

回答

思路很简单：切比雪夫距离 ≤ k 的覆盖区就是以传感器为中心、边长为 2k+12k+1 的轴对齐正方形。因此要最少传感器数，就是用边长为 s=2k+1s=2k+1 的小方块把 n×mn \times m 网格尽量紧密地平铺。行方向需要 ⌈n/s⌉\lceil n/s \rceil 个，列方向需要 ⌈m/s⌉\lceil m/s \rceil 个，总数为两者乘积。

用整数运算实现上取整：⌈a/b⌉=(a+b−1)/b\lceil a/b \rceil = (a+b-1)/b。

  • 示例1：n=m=5, k=1⇒s=3n=m=5,\ k=1\Rightarrow s=3，⌈5/3⌉=2\lceil 5/3\rceil=2，总数 2×2=42\times2=4。
  • 示例2：n=m=2, k=2⇒s=5n=m=2,\ k=2\Rightarrow s=5，⌈2/5⌉=1\lceil 2/5\rceil=1，总数 1×1=11\times1=1。

时间复杂度、空间复杂度均为 O(1)O(1)。

java
class Solution {
    public int minSensors(int n, int m, int k) {
        int side = 2 * k + 1;               // 每个传感器覆盖的正方形边长
        int rows = (n + side - 1) / side;   // 行方向需要的传感器数（上取整）
        int cols = (m + side - 1) / side;   // 列方向需要的传感器数（上取整）
        return rows * cols;
    }
}

你可以用下列用例快速自测：

  • minSensors(5, 5, 1) == 4
  • minSensors(2, 2, 2) == 1
  • minSensors(1, 1, 0) == 1
  • minSensors(3, 10, 1) == 4

分享这个问答