问题 I: 找方块
C语言题库
共 1942字，需浏览 4分钟
·
2021-04-13 02:00
问题 I: 找方块
内存限制：128 MB时间限制：1 S标准输入输出
题目描述
小明最近看到一件艺术品，是由许多黑白方块组成的矩形图，但是并不是黑白相间的。小明希望找到一个最大的黑白相间的矩形。
输入格式
第一行输入T(T<=10)。
接下来输入T组数据，每组数据第一行为N，表示这个艺术品的矩阵大小是N * N（N <=100）。
接下来是一个N * N的矩阵，0代表黑色，1代表白色。
输出格式
对于每组数据，输出最大的黑白相间矩形的面积。
每组输出占一行。
输入样例 复制
1
2
0 1
1 0
输出样例 复制
4
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define Max 105
using namespace std;
int f[Max][Max];
int s;
int main()
{
int t;
cin>>t;
while (t--)
{
s=1;
memset(f, -1, sizeof(f));
int n;
cin>>n;
for (int i=1; i<=n; i++)
for (int j=1; j<=n; j++)
scanf("%d",&f[i][j]);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
if(f[i][j]==!f[i+1][j]&&f[i][j]==!f[i][j+1])
{
int ss=1;
for (int k=j+1;k<=n; k++)
{
if(f[i][k]==!f[i][k-1])
ss++;
else
break;
}
s=max(s, ss);
for (int k=i+1; k<=n; k++)
{
if(f[k][j]==!f[k-1][j])
{
for(int z=j+1;z<=ss+j-1;z++)
{
if(f[k][z]==!f[k-1][z]&&f[k][z]==!f[k][z-1])
continue;
else
{
ss=z-j;
break;
}
}
s=max(s, ss*(k-i+1));
}
else
break;
}
}
}
printf("%d\n",s);
}
return 0;
}
评论