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

题目描述

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

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

两个单元格 (r₁, c₁) 和 (r₂, c₂) 之间的 切比雪夫距离 为 max(|r₁ − r₂|,|c₁ − c₂|)。

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

示例 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。

提示:

Python3JavaC++Go