首页 > 代码库 > codevs 1259 最大正方形子矩阵 WD
codevs 1259 最大正方形子矩阵 WD
1259 最大正方形子矩阵
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 黄金 Gold
题目描述 Description
在一个01矩阵中,包含有很多的正方形子矩阵,现在要求出这个01矩阵中,最大的正方形子矩阵,使得这个正方形子矩阵中的某一条对角线上的值全是1,其余的全是0。
输入描述 Input Description
第一行有两个整数n和m(1<=n,m<=1000)。接下来的n行,每行有m个0或1的数字。每两个数字之间用空格隔开。
输出描述 Output Description
只有一个整数,即这个满足条件的最大的正方形子矩阵的边长。
样例输入 Sample Input
4 6
0 1 0 1 0 0
0 0 1 0 1 0
1 1 0 0 0 1
0 1 1 0 1 0
样例输出 Sample Output
3
数据范围及提示 Data Size & Hint
动态规划
#include <cstdio> #include <cstring> #define ref(i,x,y)for(int i=x;i<=y;i++) #define def(i,x,y)for(int i=x;i>=y;i--) #define max(a,b)a=a>b?a:b; int n,m,ans; int a[1001][1001],f[1001][1001],s[2][1001][1001]; int main() { scanf("%d%d",&n,&m); ref(i,1,n)ref(j,1,m) scanf("%d",&a[i][j]); ref(i,1,n)ref(j,1,m) if(!a[i][j]) { s[1][i][j]=s[1][i][j-1]+1; s[0][i][j]=s[0][i-1][j]+1; } ref(i,1,n)ref(j,1,m) if(a[i][j]) { int p=f[i-1][j-1]; if(p<=s[1][i][j-1]&&p<=s[0][i-1][j]) f[i][j]=f[i-1][j-1]+1; max(ans,f[i][j]); } memset(f,0,sizeof f); ref(i,1,n)def(j,m,1) if(a[i][j]) { int p=f[i-1][j+1]; if(p<=s[1][i][j+p]&&p<=s[0][i-1][j]) f[i][j]=f[i-1][j+1]+1; max(ans,f[i][j]); } printf("%d",ans); return 0; }
codevs 1259 最大正方形子矩阵 WD
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。