[ boj : 4095 ] 최대 정사각형

www.acmicpc.net/problem/4095

4095번: 최대 정사각형

문제 : 격자판이 주어지고 1로만 이루어진 정사각형의 최대 너비 혹은 높이를 구하시오

 

해설 : DP문제입니다. 먼저 정사각형이 될 수 있는 조건부터 생각해 보면 모든 길이가 동일시 되야죠.

그러면 현재 내가 위치한 칸을 기준으로

위쪽 왼쪽 대각선 방향으로 전부 동일하다면? 정사각형이 될 수 있습니다.

이 중 공통된 길이를 택해야 되니 3가지 방향중 최소길이를 택한 후 +1 을 해주면 됩니다.

 

#include<bits/stdc++.h>

using namespace std;

int board[1000][1000], dp[1000][1000];
void solve(int n, int m);

int main()
{
	int n, m;
	while (true) {
		cin >> n >> m;
		if (n == 0 && m == 0)break;
		solve(n,m);
		memset(dp, 0, sizeof(dp));
	}
	return 0;
}
void solve(int n,int m)
{
	int ans = 0;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++) {
			cin >> board[i][j];
			dp[i][j] = board[i][j];
			ans = max(ans, dp[i][j]);
		}	
	for (int i = 1; i < n; i++)
		for (int j = 1; j < m; j++)
			if (board[i][j] == 1) {
				dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1;
				ans = max(ans, dp[i][j]);
			}
	cout << ans<<"\n";
}