题目描述
在一个n*m的只包含0和1的矩阵里找出一个不包含0的最大正方形，输出边长。
输入输出格式
输入格式：
输入文件第一行为两个整数n,m（1<=n,m<=100），接下来n行，每行m个数字，用空格隔开，0或1.
输出格式：
一个整数，最大正方形的边长
输入输出样例
输入样例#1：
4 4
0 1 1 1
1 1 1 0
0 1 1 0
1 1 0 1
输出样例#1：
2
这类问题和二维区间和的算法差不多
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<math.h>
using namespace std;
int n,m,maxn=;
int a[][],f[][];
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{
scanf("%d",&a[i][j]);
f[i][j]=f[i-][j]+f[i][j-]-f[i-][j-]+a[i][j];
}
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
for(int k=maxn;i+k<n&&j+k<m;k++)
{
int w=f[i+k][j+k]+f[i][j]-f[i+k][j]-f[i][j+k];
if(w==k*k)
maxn=max(maxn,k);
else break;
}
printf("%d",maxn);
return ;
}
题目背景
忙完了学校的事，v神终于可以做他的“正事”：陪女朋友散步。一天，他和女朋友走着走着，不知不觉就来到了一个千里无烟的地方。v神正要往回走，如发现了一块牌子，牌子上有有一行小字和一张图，小字说道：“找到图上最大的交错正方形之后和我联系，这块地就是你的了。”在房价疯长的年代，v神当然不愿错过这个机会，于是开始找了起来……以v神的能力当然找不出来了，你能帮v神找出来吗？
题目描述
图上有一个矩阵，由N*M个格子组成，这些格子由两种颜色构成，黑色和白色。请找到面积最大的且内部是黑白交错（即两个相连的正方形颜色不能相同）的正方形。
输入输出格式
输入格式：
第一行两个整数N和M，分别表示行数和列数。接下来有N行，每行M个数，0或1分别表示这个格子是黑色或白色。
输出格式：
仅有一行，表示满足条件最大正方形的 边长
输入输出样例
输入样例#1：
3 3
0 1 0
1 0 0
1 1 1
输出样例#1：
2
#include <iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
const int N=;
int n,m;
bool map[N][N];
int f[N][N];
int ans;
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
scanf("%d",&map[i][j]),f[i][j]=;
/*
for(int i=2;i<=n;i++)
if(map[1][i]!=map[1][i-1]) f[1][i]=1;
for(int i=2;i<=m;i++) f[i][1]=1;
*/
map[][]=map[][]=!map[][];
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{
if(map[i][j]!=map[i-][j] && map[i][j]!=map[i][j-])
f[i][j]=min(f[i-][j],min(f[i-][j-],f[i][j-]))+;
ans=max(ans,f[i][j]);
}
cout<<ans;
return ;
}
说明
样例解释：
(1,1)到(2,2)这个正方形是满足条件的，它的边长是2
数据范围约定：
对于30%的数据，N <= 20
对于60%的数据，N <=300
对于100%的数据，N <= 1500