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

标签: 数组 动态规划 矩阵

难度: Hard

有一个 矩形网格 状的农场，划分为 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 。

Submission

运行时间: 243 ms

内存: 19.5 MB

class Solution:
    def countPyramids(self, grid: List[List[int]]) -> int:
        # f[i][j] = min(f[i+1][j-1],f[i+1][j],f[i+1][j+1])+1

        ans = 0
        m, n = len(grid), len(grid[0])
        dp = [i-1 for i in grid[-1]]

        tmp = []
        for i in range(m-2,-1,-1):
            tmp.append(grid[i][0]-1)
            for j in range(1,n-1):
                if grid[i][j]:
                    tmp.append(1+min(dp[j-1],dp[j],dp[j+1]))
                    ans += tmp[j]
                else:
                    tmp.append(-1)
            tmp.append(grid[i][-1]-1)
            dp,tmp = tmp,[]

        dp = [i-1 for i in grid[0]]
        tmp = []

        for i in range(1,m):
            tmp.append(grid[i][0]-1)
            for j in range(1,n-1):
                if grid[i][j]:
                    tmp.append(1+min(dp[j-1],dp[j],dp[j+1]))
                    ans += tmp[j]
                else:
                    tmp.append(-1)
            tmp.append(grid[i][-1]-1)
            dp,tmp = tmp,[]
        return ans

Explain

此题解利用动态规划计算金字塔和倒金字塔的总数。定义 dp[i][j] 为以 (i, j) 为顶点的金字塔的最大可能高度。基于此定义，dp[i][j] 可由下一行的相邻三个单元格的 dp 值推导出来：dp[i][j] = min(dp[i+1][j-1], dp[i+1][j], dp[i+1][j+1]) + 1。计算从底部到顶部的金字塔数目后，类似方法可用于倒金字塔，只需改变遍历方向即可（从顶部到底部）。通过对每个可能的顶点进行分析，最终累加所有金字塔和倒金字塔的数量。

时间复杂度: O(m*n)

空间复杂度: O(n)

# Definition for the Solution class to count fertile pyramids in a grid.

class Solution:
    def countPyramids(self, grid: List[List[int]]) -> int:
        ans = 0
        m, n = len(grid), len(grid[0])

        # Initialize dp with the values of the last row (transformed for use in calculation)
        dp = [i - 1 for i in grid[-1]]

        tmp = []
        # Process each row from the bottom to the second row
        for i in range(m-2, -1, -1):
            tmp.append(grid[i][0] - 1)  # Set boundary condition
            for j in range(1, n-1):
                if grid[i][j]:  # If the cell is fertile
                    tmp.append(1 + min(dp[j-1], dp[j], dp[j+1]))
                    ans += tmp[j]
                else:
                    tmp.append(-1)  # Not fertile
            tmp.append(grid[i][-1] - 1)
            dp, tmp = tmp, []

        # Initialize for the upside-down pyramids
        dp = [i - 1 for i in grid[0]]
        tmp = []

        # Process each row from the second to the last row
        for i in range(1, m):
            tmp.append(grid[i][0] - 1)  # Set boundary condition
            for j in range(1, n-1):
                if grid[i][j]:  # If the cell is fertile
                    tmp.append(1 + min(dp[j-1], dp[j], dp[j+1]))
                    ans += tmp[j]
                else:
                    tmp.append(-1)  # Not fertile
            tmp.append(grid[i][-1] - 1)
            dp, tmp = tmp, []
        return ans

Explore

在这个算法中，使用`grid[-1]`和`grid[0]`初始化动态规划数组`dp`是因为分别计算从底部开始的金字塔和从顶部开始的倒金字塔。`grid[-1]`代表最底部的一行，`grid[0]`代表最顶部的一行。这种初始化方法确保了在计算金字塔或倒金字塔时，可以从已知的最基本情况（即最底行或最顶行的单元格直接作为金字塔的顶点，高度为1）开始计算，逐步向上或向下累计可能的更高的金字塔。这是正确的初始化方式，因为它正确地反映了金字塔顶部或底部的初始状态。

选择`min(dp[i+1][j-1], dp[i+1][j], dp[i+1][j+1]) + 1`作为更新规则是因为金字塔的每一层都需要比下一层小，并且以中心对称。因此，一个单元格 (i, j) 能形成的金字塔的最大高度，依赖于它下一行的三个相邻单元格（中间和两侧）形成的金字塔的最小高度。通过取这三个高度的最小值并加一，可以保证在当前位置 (i, j) 形成的金字塔是稳定的，并且是可能的最大高度。这种更新方式确实能够确保找到每个位置可能的最大金字塔高度。

使用tmp数组暂存计算结果的原因是为了防止在更新dp数组时覆盖还未使用的数据。如果直接在dp数组上更新，那么在计算当前行的dp值时，可能会用到已经被修改过的下一行的dp值，这会导致计算错误。使用一个临时数组tmp可以确保在整行计算完毕之前，所有需要的下一行的dp值都是未修改的，从而保证了计算的正确性。

在算法中，对于不肥沃的格子赋值为-1是用来标记这些格子不能作为金字塔的一部分。在计算dp值时，如果碰到-1，则意味着在这个位置不能形成有效的金字塔，因此任何依赖于这个位置的金字塔高度计算都会停止。这种做法有效地阻止了金字塔在不肥沃的土地上被错误地计算和累加，从而确保了算法的准确性和效率。