E - Maximum Square
Given an N x M matrix of all 1s and 0s, find the largest submatrix which is a square containing all 1s.
Input
There will be several test cases in the input. Each test case will begin with two integers, N and M (1N, M1, 000) indicating the number of rows and columns of the matrix. The next N lines will each contain M space-separated integers, guaranteed to be either 0 or 1. The input will end with a line with two 0s.
Output
For each test case, print a single integer, indicating the width (and height) of the largest square of all 1s, or 0 if there are no 1s. Print no extra spaces, and do not print any blank lines between answers.
Sample Input
4 5
0 1 0 1 1
1 1 1 1 1
0 1 1 1 0
1 1 1 1 1
3 4
1 1 1 1
1 1 1 1
1 1 1 1
6 6
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0
Sample Output
3
3
0#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 1001
#define INF 2000
using namespace std;
int main()
{
int n,m;
char g[N][N];
int ans[N][N];
int L[N],H[N];
while(scanf("%d%d",&n,&m),n!=0 || m!=0)
{
memset(g,0,sizeof(g));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&g[i][j]);
memset(ans,0,sizeof(ans));
memset(L,0,sizeof(L));
memset(H,0,sizeof(H));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(g[i][j]==0) H[i]=0; else H[i]++;
if(g[i][j]==0) L[j]=0; else L[j]=L[j]+1;
if(H[i]>ans[i-1][j-1] && L[j]>ans[i-1][j-1]) ans[i][j]=ans[i-1][j-1]+1;
else ans[i][j]=min(H[i],L[j]);
}
}
int Max=-INF;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
Max=max(Max,ans[i][j]);
printf("%d
",Max);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
cocos2d Lua 학습(一)ios에서 루아 함수 호출 및 전참 방법 lua 코드: 출력 결과: lua 호출 C++ 방법: add 함수: lua 코드: 출력 결과: 함수를 호출합니다. 함수를 호출하려면 다음 협의를 따르십시오. 우선, 호출할 함...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
