首页 > 其他分享 >【二维差分】2132. 用邮票贴满网格图

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

时间:2024-06-19 18:03:21浏览次数:22  
标签:邮票 stampHeight 2132 int stampWidth 网格 vector grid 贴满

本文涉及知识点

二维差分

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 <= 105
1 <= m * n <= 2 * 105
grid[r][c] 要么是 0 ,要么是 1 。
1 <= stampHeight, stampWidth <= 105

二维差分

邮票无限,且可以相互覆盖,能成为邮票左上角的位置,都放一张。
邮票的左上角能否放到(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++**实现。

标签:邮票,stampHeight,2132,int,stampWidth,网格,vector,grid,贴满
From: https://blog.csdn.net/he_zhidan/article/details/139365907

相关文章

  • ANSYS有限元网格划分的基本原则
    一、引言ANSYS有限元网格划分是进行数值模拟分析至关重要的一步,它直接影响着后续数值计算分析结果的精确性。网格划分涉及单元的形状及其拓扑类型、单元类型、网格生成器的选择、网格的密度、单元的编号以及几何体素。从几何表达上讲,梁和杆是相同的,从物理和数值求解上讲则是......
  • Java与服务网格(Service Mesh):构建高效微服务架构
    在微服务架构成为企业开发标准的今天,如何有效地管理众多微服务之间复杂的通信成为了一个挑战。服务网格作为一种解决方案,它通过提供一个专门的基础设施层来处理服务间通信,从而使得应用开发更加专注于业务逻辑而非通信细节。本文将介绍服务网格的基本概念,探讨其在Java环境中的应......
  • 界面控件DevExpress WinForms垂直&属性网格组件 - 拥有更灵活的UI选择(一)
    DevExpressWinForms垂直&属性网格组件旨在提供UI灵活性,它允许用户显示数据集中的单个行或在其90度倒置网格容器中显示多行数据集。另外,用户可以把它用作一个属性网格,就像在VisualStudioIDE中那样。P.S:DevExpressWinForms拥有180+组件和UI库,能为WindowsForms平台创建具有......
  • 界面控件DevExpress WinForms垂直&属性网格组件 - 拥有更灵活的UI选择(一)
    DevExpressWinForms垂直&属性网格组件旨在提供UI灵活性,它允许用户显示数据集中的单个行或在其90度倒置网格容器中显示多行数据集。另外,用户可以把它用作一个属性网格,就像在VisualStudioIDE中那样。P.S:DevExpressWinForms拥有180+组件和UI库,能为WindowsForms平台创建具有影响......
  • Star-ccm+网格划分技巧之网格类型及适用场合
    大家在进行网格划分时有没有遇到这样的情况:1、画网格时间很长;2、画网格到中途发生错误,这时候就要用到并行网格划分(ParallelMeshing)。并行网格划分(ParallelMeshing)就是使用多个内核数来加速网格生成,同时比单个内核创建更大的网格。在对大型零件进行网格划分时,此功能特别有......
  • HTML5+CSS3+JS小实例:网格图库
    实例:网格图库技术栈:HTML+CSS+JS效果:源码:【HTML】<!DOCTYPEhtml><htmllang="zh-CN"><head><metacharset="UTF-8"><metaname="viewport"content="width=device-width,initial-scale=1.0">......
  • 基于阿里云服务网格流量泳道的全链路流量管理(三):无侵入式的宽松模式泳道
    作者:尹航在前文《基于阿里云服务网格流量泳道的全链路流量管理(一):严格模式流量泳道》、《基于阿里云服务网格流量泳道的全链路流量管理(二):宽松模式流量泳道》中,我们介绍了流量泳道的概念、使用流量泳道进行全链路灰度管理的方案,以及阿里云服务网格ASM提供的严格模式与宽松模式的......
  • PyQT5之网格布局多图片显示
    选择文件夹,显示图片importosfromPyQt5importQtWidgetsfromPyQt5importQtCore,QtGuiimportsysimportcv2classButtonPanel(QtWidgets.QWidget):def__init__(self,*args,**kwargs):super().__init__(*args,**kwargs)self.image_files......
  • css网格布局
    CSS网格布局网格是一组相交的水平线和垂直线,它定义了网格的列和行。CSS提供了一个基于网格的布局系统,带有行和列,可以让我们更轻松地设计网页,而无需使用浮动和定位。以下是一个简单的网页布局,使用了网格布局,包含六列和三行:  »浏览器支持目前最新的一些浏览器版本......
  • JPanel的GridLayout布局添加网格线
        之前从网上找了许多添加网格线的方法,比如添加JLable,设置JLable文本框线实现添加网格线://初始化显示界面JFramejf=newJFrame("数独游戏");//设置窗口可视化jf.setVisible(true);//设置窗口大小jf.setSize(900,810);//将窗口显示在屏幕中央jf.setLocatio......