ACM——最大子矩阵问题——单位矩阵
单位矩阵
Time Limit: 1
010001
010000
001000
100111
2 5
01000
00110
思路：
从题来看首先分析出几点约束条件：
1、正对角线都是1
2、其余为零
由此我们可推出ff[i][j]=min(ff[i-1][j-1],min(up,left[j]))+1;
如果当前为1那它是前一个为1的个数，在判断他的上方和左连续0的个数，取最小。
代码：
#include"iostream"
using namespace std;
char f[1005][1005];
int ff[1005][1005];
int main()
{
int up,n,m;
while(cin>>n>>m){
int left[1005]={0};
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>f[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
ff[i][j]=0;
int maxx=0;
for(int i=1;i<=n;i++){
up=0;
for(int j=1;j<=m;j++){
if(f[i][j]=='1'){
ff[i][j]=min(ff[i-1][j-1],min(up,left[j]))+1;
up=0;
left[j]=0;
}
else{
ff[i][j]=0;
up++;
left[j]++;
}
}
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(maxx
cout<
}
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！