【二维差分】2132. 用邮票贴满网格图

本文涉及知识点

二维差分

LeetCode2132. 用邮票贴满网格图

给你一个 m x n 的二进制矩阵 grid ，每个格子要么为 0 （空）要么为 1 （被占据）。
给你邮票的尺寸为 stampHeight x stampWidth 。我们想将邮票贴进二进制矩阵中，且满足以下 限制 和 要求 ：
覆盖所有 空 格子。
不覆盖任何 被占据 的格子。
我们可以放入任意数目的邮票。
邮票可以相互有 重叠 部分。
邮票不允许 旋转 。
邮票必须完全在矩阵 内 。
如果在满足上述要求的前提下，可以放入邮票，请返回 true ，否则返回 false 。
示例 1：

输入：grid = [[1,0,0,0],[1,0,0,0],[1,0,0,0],[1,0,0,0],[1,0,0,0]], stampHeight = 4, stampWidth = 3
输出：true
解释：我们放入两个有重叠部分的邮票（图中标号为 1 和 2），它们能覆盖所有与空格子。
示例 2：

输入：grid = [[1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]], stampHeight = 2, stampWidth = 2
输出：false
解释：没办法放入邮票覆盖所有的空格子，且邮票不超出网格图以外。

提示：
m == grid.length
n == grid[r].length
1 <= m, n <= 10⁵
1 <= m * n <= 2 * 10⁵
grid[r][c] 要么是 0 ，要么是 1 。
1 <= stampHeight, stampWidth <= 10⁵

二维差分

邮票无限，且可以相互覆盖，能成为邮票左上角的位置，都放一张。
邮票的左上角能否放到(r,c)，则称(r,c)能否放置邮票。
两轮二维差分：
一，vDiff1记录，那些位置可以放邮票。
二，vDiff2记录那些位置已经放置了邮票或被占据。
具体：
一，如果(r,c)被占据，则左上角(r-stampHeight+1,c - stampWidth+1)，右下角为(r,c)的矩形无法放置邮票。左上角不能为负数。
二，ans1 = vDif1的结果。
三，从0到大枚举r，直到r+stampHeight<=m不成立。从0到大枚举c，直到c+stampWidth<=n不成立。
,如果vDiff[r][c]等于0,则放置邮票到vDiff2。
四，r = 0 to m-1 ,c = 0 to n-1，如果grid[r][c]=1，则vDiff.set(r,c,r+1,c+1)
五，ans2 = vDiff2的结果。
六，r = 0 to m-1 ,c = 0 to n-1，如果res2[r][c]等于0，返回fasle。
七，return true;
一四可以合并。

代码

核心代码

template<class T = int >
class CDiff2
{
public:CDiff2(int r, int c) :m_iR(r), m_iC(c) {m_vDiff.assign(m_iR, vector<T>(m_iC));}void Set(int r1, int c1, int r2Exinc, int c2Exinc, int iAdd) {m_vDiff[r1][c1] += iAdd;m_vDiff[r2Exinc][c2Exinc] += iAdd;m_vDiff[r1][c2Exinc] -= iAdd;m_vDiff[r2Exinc][c1] -= iAdd;}vector<vector<T>> Ans()const {vector<vector<T>> res(m_iR, vector<T>(m_iC));vector<T> vCols(m_iC);for (int r = 0; r < m_iR; r++) {T iSum = 0;for (int c = 0; c < m_iC; c++) {vCols[c] += m_vDiff[r][c];iSum += vCols[c];res[r][c] = iSum;}}return res;}const int m_iR, m_iC;
protected:vector<vector<T>> m_vDiff;
};class Solution {
public:bool possibleToStamp(vector<vector<int>>& grid, int stampHeight, int stampWidth) {const int R = grid.size();const int C = grid[0].size();CDiff2 diff1(R + 1, C + 1), diff2(R + 1, C + 1);for (int r = 0; r < R; r++) {for (int c = 0; c < C; c++) {if (0 == grid[r][c]) { continue; }diff1.Set(max(0, r - stampHeight + 1), max(0, c - stampWidth + 1), r + 1, c + 1, 1);diff2.Set(r, c, r + 1, c + 1, 1);				}}auto ans1 = diff1.Ans();for (int r = 0; r + stampHeight <= R; r++) {for (int c = 0; c + stampWidth <= C; c++) {if (0 == ans1[r][c]) {diff2.Set(r, c, r + stampHeight, c + stampWidth, 1);}}}auto ans2 = diff2.Ans();for (int r = 0; r < R; r++) {for (int c = 0; c < C; c++) {if (0==ans2[r][c] ) { return false; }}}return true;}
};

单元测试

template<class T1,class T2>
void AssertEx(const T1& t1, const T2& t2)
{Assert::AreEqual(t1 , t2);
}template<class T>
void AssertEx(const vector<T>& v1, const vector<T>& v2)
{Assert::AreEqual(v1.size(), v2.size());	for (int i = 0; i < v1.size(); i++){Assert::AreEqual(v1[i], v2[i]);}
}template<class T>
void AssertV2(vector<vector<T>> vv1, vector<vector<T>> vv2)
{sort(vv1.begin(), vv1.end());sort(vv2.begin(), vv2.end());Assert::AreEqual(vv1.size(), vv2.size());for (int i = 0; i < vv1.size(); i++){AssertEx(vv1[i], vv2[i]);}
}namespace UnitTest
{vector<vector<int>> grid;int stampHeight,  stampWidth;TEST_CLASS(UnitTest){public:TEST_METHOD(TestMethod0){grid = { {1,0,0,0},{1,0,0,0},{1,0,0,0},{1,0,0,0},{1,0,0,0} }, stampHeight = 4, stampWidth = 3;auto res = Solution().possibleToStamp(grid, stampHeight, stampWidth);AssertEx( true, res);}TEST_METHOD(TestMethod1){grid = { {1,0,0,0},{0,1,0,0},{0,0,1,0},{0,0,0,1} }, stampHeight = 2, stampWidth = 2;auto res = Solution().possibleToStamp(grid, stampHeight, stampWidth);AssertEx(false, res);}};
}

扩展阅读

视频课程

先学简单的课程，请移步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++**实现。