最近，我遇到了这个问题，我很想知道 1) 我是否可以将这类问题归类为一个特定的名称，或者 2) 解决这个问题的最佳方法是什么。这有点挑剔，所以请耐心等待，因为我会尽我所能解释它(提前为糟糕的绘图道歉)。
给你一个代表土壤地 block 的n x n矩阵。每个条目都有一个数值，表示使该地 block 肥沃所需的水量。您可以选择降雨的特定坐标(强度 I)，降雨面积取决于参数 d(始终为偶数) .大 d 意味着更大的面积..
挑剔的部分来了。
下雨的方式如下图所示。郊区(由绿色虚线表示)接收的降雨量 ( I/2 ) 是对应区域的一半。所以在这种情况下，它会收到 4 毫米。因此，通过决定在点 (3,3) 附近倾盆大雨，边界上将有 7 block 土壤(7 block 小于或等于 8/2 = 4 的 block )和内部(小于或等于 8) 的 10 block 地 block 导致总共 17 block 土壤变得肥沃。
问题是，给定 (n x n: 2d int array, d: int, I: int) 的参数，什么是可以肥沃的土壤的最大块数？
注意对于坐标的位置没有限制，即它可以在地形的边缘。
我是这样解决的:
基本上是蛮力，但有一些效率调整。
效率调整 1:根据 d 的值，它包含多少 block 土壤有一个限制 [d * (d/2 + 1)]。如果任何点满足最大值则停止搜索。
效率调整 2:例如，如果 d 的值为 10，则其半径将为 5，这意味着它充其量只能完全覆盖内部区域内 sqrt(5) × sqrt(5)。换句话说，它将最多完全覆盖 2 x 2，因此，我们可以从点 (2, 2) 开始搜索，而不是从 (0, 0) 开始搜索，这将不必要地浇灌空地。类似地，我们可以在对角线的对角点 (n - 2, n - 2) 处结束搜索。
这个解决方案感觉不是最优的，因为随着 d 和 n x n 变大，计算的土地有很多重叠。
最佳答案
蛮力解决方案的时间复杂度为 O(n^2 * d^2)。
一个有效的优化是使用 sliding window方法。知道给定点的灌溉值后，只需查看两个区域不同的方 block 即可计算下一个相邻点的值。这允许您将复杂度降低到 O(n^2 * d)。
事实上，通过利用问题的几何结构，您可以进一步优化此方法以实现最优的 O(n^2) 时间复杂度。 (提示:考虑沿对角线移动窗口。)细节作为练习留给读者。
进一步阅读:
关于algorithm - 这是什么类型的问题？帮忙分类，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/66147950/