백준 1915(가장 큰 정사각형)

www.acmicpc.net/problem/1915

1915번: 가장 큰 정사각형

 

이 문제도 Rebro님이 추천해주신 문제

 

10109 Troyangles랑 비슷한 유형의 2차원 dp문제이다. 

 

dp가 된다는 것을 알면 이제 남은건 간단하다 dp가 되는 규칙찾기 

 

이 문제는 i,j가 정사각형의 맨왼쪽위로 설정한뒤에 앞선 문제와 동일한 방식으로 dp 테이블을 채워 나가면 된다.

 

dp[i][j] = min(dp[i+1][j+1], dp[i+1][j], dp[i][j+1]) +1 

 

#include<iostream>
#include<algorithm>
using namespace std;
#define MAX 1005

int mat[MAX][MAX];
int dp[MAX][MAX];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			char a;
			cin >> a;
			mat[i][j] = a - '0';
		}
	}
	int ans = 0;
	for (int i = n - 1; i >= 0; i--) {
		for (int j = m - 1; j >= 0; j--) {
			if (mat[i][j] == 0)continue;
			dp[i][j] = min({ dp[i + 1][j + 1], dp[i + 1][j], dp[i][j + 1] })+1;
			ans = max(ans, dp[i][j]);
		}
	}
	cout << ans*ans;
}