当前位置：首页 > article >正文

【C++动态规划】2088. 统计农场中肥沃金字塔的数目|2104

article 2025/1/5 13:26:26

本文涉及知识点

C++动态规划

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

有一个矩形网格状的农场，划分为 m 行 n 列的单元格。每个格子要么是肥沃的（用 1 表示），要么是贫瘠的（用 0 表示）。网格图以外的所有与格子都视为贫瘠的。
农场中的金字塔区域定义如下：
区域内格子数目大于 1 且所有格子都是肥沃的。
金字塔顶端是这个金字塔最上方的格子。金字塔的高度是它所覆盖的行数。令 (r, c) 为金字塔的顶端且高度为 h ，那么金字塔区域内包含的任一格子 (i, j) 需满足 r <= i <= r + h - 1 且 c - (i - r) <= j <= c + (i - r) 。
一个倒金字塔类似定义如下：
区域内格子数目大于 1 且所有格子都是肥沃的。
倒金字塔的顶端是这个倒金字塔最下方的格子。倒金字塔的高度是它所覆盖的行数。令 (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 <= 10⁵
grid[i][j] 要么是 0 ，要么是 1 。

动态规划

先求正金字塔数量，然后第i行和R-1-i行互换，i $[0,R/2-1]，再求正金字塔数量。
#动态规划的装表示
H金字 = min((C+1)/2,R)

动态规划的状态表示

dp[h][r][c]表示以(r,c)为顶，高度为h的正金子塔是否存在。 空间复杂度：O(RCH)

动态规划的填表顺序

h = 2 To H r = 0 To r+h <= R c to 0 To c+h <= C
dp[h][r][c] = grid[r][c]&&grid[r+1][c]&&[h-1]dp[r+1][c-1]&&dp[h-1][r+1][c+1]
单个状态的时间复杂度：O(1)，总时间复杂度：O(RCH)

动态规划的初始化

dp[1] = grid[r][c]
可用滚动向量

动态规划的返回值

dp[2…H]之和。

代码

核心代码

class Solution {
		public:
			int countPyramids(vector<vector<int>>& grid) {
				const int R = grid.size();
				auto rev = grid;
				for (int r = 0; r < R / 2; r++) {
					rev[r].swap(rev[R - 1 - r]);
				}
				return Do(grid) + Do(rev);
			}
			int Do(const vector<vector<int>>& grid) {
				const int R = grid.size();
				const int C = grid[0].size();
				const int H = min(R, (C + 1) / 2);
				auto pre = grid;
				int ans = 0;
				for (int h = 2; h <= H; h++) {
					vector<vector<int>> cur(R, vector<int>(C));
					for(int r = 0 ; r+ h  <= R ;r++)
						for (int c = h-1; c + h <= C; c++) {
							cur[r][c] = pre[r][c] && pre[r + 1][c - 1] && pre[r + 1][c] && pre[r + 1][c + 1];
							ans += cur[r][c];
						}
					pre.swap(cur);
				}
				return ans;
			}
		};

单元测试

vector<vector<int>> grid;
		TEST_METHOD(TestMethod11)
		{
			grid = { {0,1,1,0},{1,1,1,1} };
			auto res = Solution().countPyramids(grid);
			AssertEx(2, res);
		}
		TEST_METHOD(TestMethod12)
		{
			grid = { {1,1,1},{1,1,1} };
			auto res = Solution().countPyramids(grid);
			AssertEx(2, res);
		}
		TEST_METHOD(TestMethod13)
		{
			grid = { {1,0,1},{0,0,0},{1,0,1} };
			auto res = Solution().countPyramids(grid);
			AssertEx(0, res);
		}
		TEST_METHOD(TestMethod14)
		{
			grid = { {1,1,1,1,0},{1,1,1,1,1},{1,1,1,1,1},{0,1,0,0,1} };
			auto res = Solution().countPyramids(grid);
			AssertEx(13, res);
		}
		TEST_METHOD(TestMethod15)
		{
			grid.assign(1000, vector<int>(100, 1));
			auto res = Solution().countPyramids(grid);
			AssertEx(4816700 , res);
		}

优化

如果(r,c,h)是金子塔，则(r,c,h-1)也是金子塔。

动态规划的状态表示

dp[r][c]记录最大h。空间复杂度：O(mn)

动态规划的填表顺序

r = R-2 to 0 c = 1 to C-2

动态规划的转移方程

$\begin{cases} dp[r][c] = 0 && 0 == grid[r][c] \\ dp[r][c] = 1 +min(dp[r+1][c-1]+dp[r+1][c]+dp[r+1][c+1]) && other\\ \end{cases}$
空间复杂度：O(mn)

动态规划的初始值

dp = grid

动态规划的返回值

dp之和-gird之和

代码

class Solution {
		public:
			int countPyramids(vector<vector<int>>& grid) {
				const int R = grid.size();
				auto rev = grid;
				for (int r = 0; r < R / 2; r++) {
					rev[r].swap(rev[R - 1 - r]);
				}
				return Do(grid) + Do(rev);
			}
			int Do(const vector<vector<int>>& grid) {
				const int R = grid.size();
				const int C = grid[0].size();
				auto dp = grid;	
				for(int r = R-2 ;r >= 0 ; r--)
					for (int c = 1; c < C - 1; c++) {
						if (0 == grid[r][c]) { continue; }
						dp[r][c] = 1 + *min_element(dp[r+1].begin() + c - 1, dp[r+1].begin() + c + 2);
					}
				int ans = 0;
				for (const auto& v : dp) {
					ans += accumulate(v.begin(), v.end(),0);
				}
				for (const auto& v : grid) {
					ans -= accumulate(v.begin(), v.end(), 0);
				}
				return ans;
			}
		};

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功成功+反思=成功