BOJ 1915 가장 큰 정사각형

www.acmicpc.net/problem/1915 

1915번: 가장 큰 정사각형

 

정사각형을 만족하기 위해서 어떤 규칙이 필요할까?

행렬 i, j 를 기준으로 왼쪽, 위, 왼쪽 위가 모두 1인 것만이 정사각형이 된다.

이걸 확장시켜주면, 최종적인 점화식은 \(D[i][j] = min(d[i-1][j], d[i][j-1], d[i-1][j-1]) + 1\) 이 된다.

물론 조건문으로 현재 위치가 1이고 그 주변도 1임을 미리 따져줘야 한다.

 

 

#include <cstdio>
#include <algorithm>
using namespace std;
 
int a[1001][1001], n, m;
 
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            scanf("%1d", &a[i][j]);
 
    int res = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (a[i][j] && a[i - 1][j] && a[i][j - 1] && a[i - 1][j - 1]) {
                a[i][j] += min({ a[i][j - 1], a[i - 1][j - 1], a[i - 1][j] });
            }
            res = max(res, a[i][j]);
        }
    }
    printf("%d\n", res * res);
    
    return 0;
}

 

a 배열에는 정사각형을 만족하는 크기가 들어가 있을테니 제곱의 형태로 출력해주면 된다.