题解 # 二维矩阵最大矩形问题#
题目：
小明有一张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个数一样的组合即可。
