2088-统计农场中肥沃金字塔的数目

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:32 2023-09-13 16:06:32 Updated    

有一个 矩形网格 状的农场，划分为 m 行 n 列的单元格。每个格子要么是 肥沃的 （用 1 表示），要么是 贫瘠
的（用 0 表示）。网格图以外的所有与格子都视为贫瘠的。

农场中的 金字塔 区域定义如下：

  1. 区域内格子数目 **大于 **1 且所有格子都是 肥沃的 。
  2. 金字塔 顶端 是这个金字塔 最上方 的格子。金字塔的高度是它所覆盖的行数。令 (r, c) 为金字塔的顶端且高度为 h ，那么金字塔区域内包含的任一格子 (i, j) 需满足 r <= i <= r + h - 1 且 c - (i - r) <= j <= c + (i - r) 。

一个 倒金字塔 类似定义如下：

  1. 区域内格子数目 大于 1 且所有格子都是 肥沃的 。
  2. 倒金字塔的 顶端 是这个倒金字塔 最下方 的格子。倒金字塔的高度是它所覆盖的行数。令 (r, c) 为金字塔的顶端且高度为 h ，那么金字塔区域内包含的任一格子 (i, j) 需满足 r - h + 1 <= i <= r 且 c - (r - i) <= j <= c + (r - i) 。

下图展示了部分符合定义和不符合定义的金字塔区域。黑色区域表示肥沃的格子。

给你一个下标从 0 开始且大小为 m x n 的二进制矩阵 grid ，它表示农场，请你返回 grid 中金字塔和倒金字塔的
总数目 。

示例 1：



**输入：** grid = [[0,1,1,0],[1,1,1,1]]
**输出：** 2
**解释：**
2 个可能的金字塔区域分别如上图蓝色和红色区域所示。
这个网格图中没有倒金字塔区域。
所以金字塔区域总数为 2 + 0 = 2 。

示例 2：



**输入：** grid = [[1,1,1],[1,1,1]]
**输出：** 2
**解释：**
金字塔区域如上图蓝色区域所示，倒金字塔如上图红色区域所示。
所以金字塔区域总数目为 1 + 1 = 2 。

示例 3：

**输入：** grid = [[1,0,1],[0,0,0],[1,0,1]]
**输出：** 0
**解释：**
网格图中没有任何金字塔或倒金字塔区域。

示例 4：




**输入：** grid = [[1,1,1,1,0],[1,1,1,1,1],[1,1,1,1,1],[0,1,0,0,1]]
**输出：** 13
**解释：**
有 7 个金字塔区域。上图第二和第三张图中展示了它们中的 3 个。
有 6 个倒金字塔区域。上图中最后一张图展示了它们中的 2 个。
所以金字塔区域总数目为 7 + 6 = 13.

提示：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 1000
  • 1 <= m * n <= 105
  • grid[i][j] 要么是 0 ，要么是 1 。

方法一：动态规划

思路与算法

我们首先考虑所有的「金字塔」。

如果我们能够计算出以每一个位置 (i, j) 为顶端的最大的金字塔的高度：

这里我们对于高度的定义如下：

  • 如果 (i, j) 本身不是肥沃的，那么最大的金字塔的高度为 -1；
  • 如果 (i, j) 本身是肥沃的，但是它无法作为任何金字塔的顶端，那么最大的金字塔的高度为 0；
  • 如果 (i, j) 本身是肥沃的，并且以它为顶端的最大金字塔有 x 行，那么最大的金字塔的高度为 x-1。

记为 f[i, j]，那么只要 (i, j) 本身是肥沃的，那么以 (i, j) 为顶端的金字塔的高度就可以为 1, 2, \cdots, f[i, j]，即一共有 f[i, j] 个金字塔。此时，所有 f[i, j] 的和即为金字塔的总数。

要想求出 f[i, j]，我们可以考虑形成金字塔的充要条件。要想形成一个以 (i, j) 为顶端并且高度为 x 的金字塔，当且仅当：

  • f[i, j] 本身是肥沃的；

  • 存在以 (i+1, j-1) 为顶端，高度为 x-1 的金字塔；

  • 存在以 (i+1, j) 为顶端，高度为 x-1 的金字塔；

  • 存在以 (i+1, j+1) 为顶端，高度为 x-1 的金字塔；

fig1

上图可视化地描述了这四个条件。这说明 x 的最大值取决于 (i, j) 下方左中右三个位置为顶端的金字塔高度的最小值，因此：

  • 如果 (i, j) 本身不是肥沃的，那么 f[i, j] = -1；

  • 如果 (i, j) 本身是肥沃的，那么有：

    f[i, j] = \min \big{ f[i+1, j-1], f[i+1, j], f[i+1, j+1] \big} + 1

这里规定所有超出边界的 f[i, j] 的值均为 -1。

而在考虑「倒金字塔」时，由于它只是把金字塔倒过来，因此我们只需要把上面的状态转移方程中的 i+1 全部改成 i-1 即可：

f[i, j] = \min \big{ f[i-1, j-1], f[i-1, j], f[i-1, j+1] \big} + 1

代码

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
    int countPyramids(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> f(m, vector<int>(n));
        int ans = 0;
        // 金字塔
        for (int i = m - 1; i >= 0; --i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 0) {
                    f[i][j] = -1;
                }
                else if (i == m - 1 || j == 0 || j == n - 1) {
                    f[i][j] = 0;
                }
                else {
                    f[i][j] = min({f[i + 1][j - 1], f[i + 1][j], f[i + 1][j + 1]}) + 1;
                    ans += f[i][j];
                }
            }
        }
        // 倒金字塔
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 0) {
                    f[i][j] = -1;
                }
                else if (i == 0 || j == 0 || j == n - 1) {
                    f[i][j] = 0;
                }
                else {
                    f[i][j] = min({f[i - 1][j - 1], f[i - 1][j], f[i - 1][j + 1]}) + 1;
                    ans += f[i][j];
                }
            }
        }
        
        return ans;
    }
};
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
    def countPyramids(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        f = [[0] * n for _ in range(m)]
        ans = 0

        # 金字塔
        for i in range(m - 1, -1, -1):
            for j in range(n):
                if grid[i][j] == 0:
                    f[i][j] = -1
                elif i == m - 1 or j == 0 or j == n - 1:
                    f[i][j] = 0
                else:
                    f[i][j] = min(f[i + 1][j - 1], f[i + 1][j], f[i + 1][j + 1]) + 1
                    ans += f[i][j]
        
        # 倒金字塔
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 0:
                    f[i][j] = -1
                elif i == 0 or j == 0 or j == n - 1:
                    f[i][j] = 0
                else:
                    f[i][j] = min(f[i - 1][j - 1], f[i - 1][j], f[i - 1][j + 1]) + 1
                    ans += f[i][j]
        
        return ans

复杂度分析

  • 时间复杂度：O(mn)。

  • 空间复杂度：O(mn)，即为存储所有状态需要的空间。注意到在两种状态转移方程中，f[i, j] 只会从 f[i-1, ..] 或者 f[i+1, ..] 转移而来，因此可以使用两个长度为 n 的一维数组交替地进行状态转移，空间复杂度可以降低为 O(n)。

 Comments
On this page
2088-统计农场中肥沃金字塔的数目