P1681 最大正方形 Iand II

题目描述

在一个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=1; int a[110][110],f[110][110]; int main() {scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){scanf("%d",&a[i][j]);f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+a[i][j]; }for(int i=1;i<=n;i++)for(int j=1;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 0; }

题目背景

忙完了学校的事，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=1509; int n,m; bool map[N][N]; int f[N][N]; int ans; int main() {scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++) scanf("%d",&map[i][j]),f[i][j]=1;/*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[0][1]=map[1][0]=!map[1][1];for(int i=2;i<=n;i++)for(int j=2;j<=m;j++){if(map[i][j]!=map[i-1][j] && map[i][j]!=map[i][j-1])f[i][j]=min(f[i-1][j],min(f[i-1][j-1],f[i][j-1]))+1;ans=max(ans,f[i][j]);}cout<<ans;return 0; }

 

说明

样例解释：

(1,1)到(2,2)这个正方形是满足条件的，它的边长是2

数据范围约定：

对于30%的数据，N <= 20

对于60%的数据，N <=300

对于100%的数据，N <= 1500

 

转载于:https://www.cnblogs.com/CLGYPYJ/p/7737943.html

总结

以上是生活随笔为你收集整理的P1681 最大正方形 Iand II的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。