<백준 알고리즘> 1915번: 가장 큰 정사각형

문제

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;
}