문제
n×m의 0, 1로 된 배열이 있다. 이 배열에서 1로 된 가장 큰 정사각형의 크기를 구하는 프로그램을 작성하시오.
0 | 1 | 0 | 0 |
0 | 1 | 1 | 1 |
1 | 1 | 1 | 0 |
0 | 0 | 1 | 0 |
위와 같은 예제에서는 가운데의 2×2 배열이 가장 큰 정사각형이다.
입력
첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다.
출력
첫째 줄에 가장 큰 정사각형의 넓이를 출력한다.
예제 입력 1
4 4 0100 0111 1110 0010 |
예제 출력 1
4 |
더보기
Solution
#include<stdio.h>
#include<stdlib.h>
int min(int x,int y,int z)
{
return x<=y&&x<=z?x:y<=x&&y<=z?y:z;
}
int main(void)
{
int n, m, **board=NULL, max=0;
scanf("%d %d", &n, &m);
board=(int **)malloc((n+1)*sizeof(int *));
for(int i=0;i<=n;i++)
board[i]=(int *)calloc(m+1,sizeof(int));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
scanf("%1d", &board[i][j]);
if(board[i][j]==1)
board[i][j]=min(board[i-1][j-1],board[i-1][j],board[i][j-1])+1;
max=board[i][j]>max?board[i][j]:max;
}
printf("%d\n", max*max);
for(int i=0;i<=n;i++)
free(board[i]);
free(board);
return 0;
}
728x90
'백준 알고리즘' 카테고리의 다른 글
<백준 알고리즘> 15720번: 카우버거 (0) | 2021.01.31 |
---|---|
<백준 알고리즘> 2116번: 주사위 쌓기 (0) | 2021.01.31 |
<백준 알고리즘> 1459번: 걷기(틀림) (0) | 2021.01.30 |
<백준 알고리즘> 20152번: Game Addiction(틀림) (0) | 2021.01.24 |
<백준 알고리즘> 20540번: 연길이의 이상형 (0) | 2021.01.24 |