题目:
小明有一张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;
}
效果演示:
文章来源:https://www.toymoban.com/news/detail-466273.html
拓展:
求正方形该代码也使用,查找 下方0个数和右边0个数一样的组合即可。文章来源地址https://www.toymoban.com/news/detail-466273.html
到了这里,关于题解 # 二维矩阵最大矩形问题#的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!