本文涉及知识点
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 <= 105
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
动态规划的转移方程
{
d
p
[
r
]
[
c
]
=
0
0
=
=
g
r
i
d
[
r
]
[
c
]
d
p
[
r
]
[
c
]
=
1
+
m
i
n
(
d
p
[
r
+
1
]
[
c
−
1
]
+
d
p
[
r
+
1
]
[
c
]
+
d
p
[
r
+
1
]
[
c
+
1
]
)
o
t
h
e
r
\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}
{dp[r][c]=0dp[r][c]=1+min(dp[r+1][c−1]+dp[r+1][c]+dp[r+1][c+1])0==grid[r][c]other
空间复杂度：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;
}
};
扩展阅读
| 我想对大家说的话 |
|---|
| 工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。 |
| 学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作 |
| 有效学习：明确的目标 及时的反馈 拉伸区（难度合适） 专注 |
| 闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
| 失败+反思=成功 成功+反思=成功 |
视频课程
先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。