题解 # 二维矩阵最大矩形问题#

这篇具有很好参考价值的文章主要介绍了题解 # 二维矩阵最大矩形问题#。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目:

小明有一张N*M的方格纸,且部分小方格中涂了颜色,部分小方格还是空白。


给出N (2<Ns30)和M(2sMs30)的值,及每个小方格的状态((被涂了颜色小方格用数字1表示,空白小方格用数字0表示);

请帮助小明找出最大的矩形空白区域,并输出该矩形空白区域由多少个小方格组成。


例如:N=4, M=5,4*5的方格纸中每个小方格的状态如下图:

题解 # 二维矩阵最大矩形问题# 

最大的空日区域由6个小方格组成(红色框区域)。

思路:

暴力穷举法:

1、将每一个方格的下边0的个数、右边0的个数进行统计

2、在由下边0的个数和右边0的个数以及该方格围城的矩形中,筛选出值是1的方格,进行0个数的回退。

3、将每一个方格的下标、下边0的个数,右边0的个数进行保存,最后再求最大的面积

4、如果这个方格里面是1则,从该方格出发是不能构成数据全部为0的矩形的,行刺可以直接将该方格的下边0和右边0的个数设置为0,排除即可。

5、最后查找 下边0的个数 >= 1   同时   右边0的个数也 >= 1的找到面积最大的矩形。

代码:

#include<stdio.h>
#define N 4
#define M 5 
#define NUM (N*M)

int main()
{
	int arr[N][M] = {
		{1,1,0,0,0},
		{1,0,1,0,0},
		{0,0,0,1,1},
		{0,0,0,1,0},
	};
	
	//  本例采用数组存储,因为有多个数组因此采用 二维数组方式
	int posArr[NUM][4]={0};
	
	// 先获取每一个数据
	// arr数据的行下标 
	int i;
	// arr数据的列下标 
	int j;
	
	printf("原始数组信息:\n");
	for(i=0;i<N;i++)
	{
		for(j=0;j<M;j++)
		{
			printf("%d ",arr[i][j]); 
		}
		printf("\n");
	}
	
	// 查找下边0的临时下标 
	int k;
	// 查找右边0的临时下标 
	int t;
	
	// 下边0的个数 
	int bottom = 0;
	// 右边0的个数 
	int right = 0;
	
	// 存放最大矩形信息的下标。
	int maxI;
	// 最大矩形的面积 
	int maxArea;
	
	for(i=0;i<N;i++)
	{
		for(j=0;j<M;j++)
		{				
			// 如果该数据是1,不能构成以这个点为定点的矩形,则不需要向下和向右统计0的个数了 
			if(arr[i][j] != 0)
			{
				posArr[i*M+j][0] = i; 
				posArr[i*M+j][1] = j; 
				posArr[i*M+j][2] = 0; 
				posArr[i*M+j][3] = 0; 
				continue;
			}
			
			// 如果该数据是0,可能构成 以这个点为定点的矩形
			bottom = 0;
			right = 0;
			// 查找下边0的个数;
			for(k=j+1;k<M;k++)
			{
				if(arr[i][k] == 0)
				{
					right++;
				}
				else
				{
					break;
				}
			} 
			
			// 向右查找0的个数
			for(t=i+1;t<N;t++)
			{
				if(arr[t][j] == 0)
				{
					bottom++;
				}
				else
				{
					break;
				}
			} 
			
			// 以行为准查找1,将不和要求的矩形排除掉,当前位置为i 和 j		
			for(k=i+1;k<=i + bottom;k++)
			{
				for(t=j;t<=j + right;t++)
				{
					if(arr[k][t] == 1)
					{
						if(k > t)
						{
							bottom -= 1;
						}
						else if(k < t)
						{
							right -= 1;
						}
						else
						{
							bottom -= 1;
							right  -= 1;
						}
					}
				}
			} 			
				 
			posArr[i*M+j][0] = i; 
			posArr[i*M+j][1] = j; 
			posArr[i*M+j][2] = bottom; 
			posArr[i*M+j][3] = right; 
		}	
	} 	

	// 访问数据
	maxI = 0;
	maxArea=0; 
	int tempArea = 0;
	for(i=0;i<NUM;i++)
	{
		if(posArr[i][2] == 0 && posArr[i][3] != 0)
		{
			tempArea = 1 * posArr[i][3];
		}
		
		if(posArr[i][2] != 0 && posArr[i][3] == 0)
		{
			tempArea = 1 * posArr[i][2];
		}
		
		if(posArr[i][2] == 0 && posArr[i][3] == 0)
		{
			tempArea = 1;
		}
		
		if(posArr[i][2] != 0 && posArr[i][3] != 0)
		{
			tempArea = (posArr[i][2]+1) * (posArr[i][3]+1);
		}
		
		if(maxArea < tempArea)
		{
			maxI = i;
			maxArea = tempArea;
		}			
	} 
	
	printf("最大矩形的信息:\n");
	printf("左上角的坐标点为:第%d行第%d列\n",posArr[maxI][0],posArr[maxI][1]);
	printf("宽:%d,高%d\n",posArr[maxI][3]+1,posArr[maxI][2]+1);
	printf("面积为:%d\n",(posArr[maxI][3]+1)*(posArr[maxI][2]+1));
	 
	return 0;
}

效果演示:

题解 # 二维矩阵最大矩形问题#

题解 # 二维矩阵最大矩形问题# 

 题解 # 二维矩阵最大矩形问题#

拓展:

求正方形该代码也使用,查找 下方0个数和右边0个数一样的组合即可。文章来源地址https://www.toymoban.com/news/detail-466273.html

到了这里,关于题解 # 二维矩阵最大矩形问题#的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 华为OD机试 - 二维矩阵的最大值(Python)

    给定一个仅包含 0 和 1 的 n*n 二维矩阵 请计算二维矩阵的最大值 计算规则如下 每行元素按下标顺序组成一个二进制数(下标越大约排在低位), 二进制数的值就是该行的值,矩阵各行之和为矩阵的值 允许通过向左或向右整体循环移动每个元素来改变元素在行中的位置 比如 [

    2024年02月12日
    浏览(54)
  • [USACO11MAR] Brownie Slicing G题解(二分+二维前缀和+矩阵分割)

    题目地址 P3017 [USACO11MAR] Brownie Slicing G 二分最大化最小值 切割思路: 一行一行进行切割,如果这一行可以切割出b块大于等于mid的块,就开始切割下一行 如果无法切割出b块,就把正在切割的行与下一行拼起来一起切割 最后通过能切割出b块的水平块块够不够a条来判断m是否合

    2024年02月07日
    浏览(38)
  • Python获取二维数组(矩阵)第二列值与最大值

    对于二维数组(矩阵)的应用有多广与多重要,怎么研究都不为过,突然想获取其中最大的一组值,发现max返回的是第一列最大值的这组数,如何获得第二列最大的这组数呢? 比如: A=[[1, 2], [12, 22], [22, 5], [22, 50], [122, 50], [330, 3], [4, 400], [34, 56], [3, 44]] 如果max(A),返回的是[330, 3

    2024年02月06日
    浏览(49)
  • 吃透单调栈(2)——解两道Hard题:接雨水、柱状图中最大的矩形问题

    这类题目的数据通常是一维数组,要寻找任一个元素的 右边或者左边 第一个 比自己 大 或者 小 的元素的位置(寻找 边界 ) ,此时我们就要想到可以用单调栈了。   这道题就是要求解每一个柱子左边第一个比它高的柱子,以及右边第一个比它高的柱子,然后这两个柱子间

    2024年02月10日
    浏览(35)
  • 利用二维数组输出一个3*4的矩阵的最大值及其所在的行、列

    利用二维数组输出一个3*4的矩阵的最大值及其所在的行、列 要输出矩阵如下: 核心:定义一个最大值的标志,一般我们把数组的第一个位置的数赋给最大值标志,然后遍历二维数组,每遍历到一个数时,将其与标志进行比较,若大于最大值标志,则将其的值赋给最大值标志

    2024年01月23日
    浏览(50)
  • 【LeetCode热题100】打卡第42天:滑动窗口最大值&搜索二维矩阵II

    大家好,我是知识汲取者,欢迎来到我的LeetCode热题100刷题专栏! 精选 100 道力扣(LeetCode)上最热门的题目,适合初识算法与数据结构的新手和想要在短时间内高效提升的人,熟练掌握这 100 道题,你就已经具备了在代码世界通行的基本能力。在此专栏中,我们将会涵盖各种

    2024年02月10日
    浏览(48)
  • 【免费题库】华为OD机试 - 最大坐标值、小明的幸运数(Java & JS & Python & C & C++)

    哈喽,本题库完全免费,收费是为了防止被爬,大家订阅专栏后可以私信联系退款。感谢支持 小明在玩一个游戏,游戏规则如下: 在游戏开始前,小明站在坐标轴原点处(坐标值为0). 给定一组指令和一个幸运数,每个指令都是一个整数,小明按照指令前进指定步数或者后

    2024年04月09日
    浏览(76)
  • 详解Leetcode中关于malloc模拟开辟二维数组问题,涉及二维数组的题目所给函数中的各个参数的解读

    最近博主一直再刷Leetcode上有关c语言的题目,有些题目第一步就将我卡死了。为什么呢?因为题目中所给的函数里的参数的具体含义我既然都不知道是什么意思。当然在请教了一些大佬后我也顺利解决了,不然也不会有人和你们分享了,哈哈哈~ 我就已一个典型的题目来介绍

    2024年02月08日
    浏览(44)
  • 【洛谷 P1029】[NOIP2001 普及组] 最大公约数和最小公倍数问题 题解(更相减损术)

    输入两个正整数 x 0 , y 0 x_0, y_0 x 0 ​ , y 0 ​ ,求出满足下列条件的 P , Q P, Q P , Q 的个数: P , Q P,Q P , Q 是正整数。 要求 P , Q P, Q P , Q 以 x 0 x_0 x 0 ​ 为最大公约数,以 y 0 y_0 y 0 ​ 为最小公倍数。 试求:满足条件的所有可能的 P , Q P, Q P , Q 的个数。 一行两个正整数 x 0 , y 0

    2024年02月09日
    浏览(43)
  • 回型矩阵|蛇形矩阵|上三角矩阵|矩阵转置|二维数组打印问题

    二维数组,作为一种存放一系列数的载体,不免和数学中用于存放数的数表——矩阵,有着密切的联系。矩阵本身就有些抽象,需要设计一个程序精准打印出来更是有难度,所以今天便来总结一些二维数组与矩阵打印的问题该如何解决。 (题目取自牛客网BC133-BC138) 给你一个

    2024年02月03日
    浏览(49)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包