列表

详情

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

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

 

提示：

原站题解

去查看

上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution { public: int countPyramids(vector<vector<int>>& grid) { } };

python3 解法, 执行用时: 572 ms, 内存消耗: 19.8 MB, 提交时间: 2023-09-21 10:22:13 

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

cpp 解法, 执行用时: 72 ms, 内存消耗: 31.8 MB, 提交时间: 2023-09-21 10:21:28 

class Solution {
public:
    int countPyramids(vector<vector<int>>& grid) {
        int ans = 0;
        int m = grid.size(), n = grid[0].size();

        // 正序遍历
        ans += reverse(grid);

        // 转置
        for (int i = 0; i < m / 2; ++i) {
            for (int j = 0; j < n; ++j) {
                swap(grid[i][j], grid[m - i - 1][j]);
            }
        }

        // 逆序遍历 计算反方向的金字塔个数
        ans += reverse(grid);

        return ans;
    }

    int reverse(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int ans = 0;
        int f[m][n];
        memset(f, 0, sizeof(f));

        // 最底层初始化
        for (int i = m - 1, j = 0; j < n; ++j) {
            f[i][j] = grid[i][j];
        }

        // 从倒数第二层开始
        for (int i = m - 2; i >= 0; --i) {
            // 左右两边没有左右下角
            f[i][0] = grid[i][0];
            f[i][n - 1] = grid[i][n - 1];

            for (int j = 1; j < n - 1; ++j) {
                if (grid[i][j] == 0) {
                    f[i][j] = 0;
                } else {
                    f[i][j] = min(f[i + 1][j], min(f[i + 1][j + 1], f[i + 1][j - 1])) + 1;
                    // 只有1层以上的金字塔才能构成一个答案
                    ans += f[i][j] - 1;
                }
            }
        }

        return ans;
    }
};

python3 解法, 执行用时: 404 ms, 内存消耗: 19.7 MB, 提交时间: 2023-09-21 10:21:05 

class Solution:
    def countPyramids(self, grid: List[List[int]]) -> int:
        R,C = len(grid), len(grid[0])
        def calc():
            dp = [ [] for _ in range(R)]
            res = 0
            for r in range(R):
                dp[r] = grid[r][:]
            for r in range(1,R):
                for c in range(1, C-1):
                    if grid[r][c]:
                        dp[r][c] = min(dp[r-1][c-1],dp[r-1][c+1],dp[r-1][c]) + 1
                        res += dp[r][c] -1
            return res
        res = calc()
        for r in range(R//2):
            grid[r],grid[R-1-r] =  grid[R-1-r],grid[r]
        res += calc()
        return res

golang 解法, 执行用时: 72 ms, 内存消耗: 7.4 MB, 提交时间: 2023-09-21 10:20:54 

func countPyramids(grid [][]int) (ans int) {
	m, n := len(grid), len(grid[0])
	dp := make([][]int, m) // 表示金字塔顶端位于 (i,j) 时的最大层数（1 层也算）
	for i := range dp {
		dp[i] = make([]int, n)
	}

	f := func() {
		dp[m-1] = grid[m-1]
		for i := m - 2; i >= 0; i-- {
			dp[i][0] = grid[i][0]
			dp[i][n-1] = grid[i][n-1]
			for j := 1; j < n-1; j++ {
				if grid[i][j] == 0 {
					dp[i][j] = 0
				} else {
					dp[i][j] = min(min(dp[i+1][j-1], dp[i+1][j+1]), dp[i+1][j]) + 1
					ans += dp[i][j] - 1
				}
			}
		}
	}
	f() // 求正金字塔个数
	for i := 0; i < m/2; i++ { // 上下颠倒
		grid[i], grid[m-1-i] = grid[m-1-i], grid[i]
	}
	f() // 再求一遍正金字塔个数
	return
}

func min(a, b int) int { if a > b {return b}; return a }

上一题

© 2024 leetcode.cn