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

news/2024/10/19 12:43:38/

题目：

小明有一张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;
}