【二维差分】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

我想对大家说的话
《喜缺全书算法册》以原理、正确性证明、总结为主。
按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛