BOJ)1460 진욱이의 농장

문제: icpc.me/1460 

n*n 크기의 격자에 씨를 뿌리는 방법이 주어지고 격자에서 임의의 정사각형을 선택하여 정사각형 내부의 점에 서로 다른 씨앗이 최대 2개가 되도록 정사각형을 선택할 때 가장 넓은 정사각형의 넓이를 출력하는 문제이다.

씨앗의 종류인 F의 범위가 0~7인걸 이용하여

F^2+F로 모든 경우의 씨앗을 정한다면 

현재 상태에서 해당하는 씨앗이 뿌려져있는 가장 넓은 정사각형을 구하는 문제로 치환하여 풀 수 있다.

이는 다이나믹 프로그래밍을 이용하여 n^2에 해결할 수 있다.

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int res, a[1010][1010], n, m, b[1010][1010];
int main() {
    scanf("%d%d", &n, &m);
    n++;
    while (m--) {
        int x, y, z, w;
        scanf("%d%d%d%d", &x, &y, &z, &w);
        for (int i = x; i < x + z; i++) {
            for (int j = y; j < y + z; j++)
                a[i][j] = w;
        }
    }
    for (int curr = 1; curr <= 7; curr++) {
        for (int curr2 = curr; curr2 <= 7; curr2++) {
            memset(b, 0, sizeof(b));
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++)
                    if (curr == a[i][j] || curr2 == a[i][j])b[i][j] = 1;
            }
            for (int i = 1; i < n; i++) {
                for (int j = 1; j < n; j++) {
                    if (!b[i][j])continue;
                    b[i][j] = min(b[i - 1][j], min(b[i - 1][j - 1], b[i][j - 1])) + 1;
                    res = max(res, b[i][j]);
                }
            }
        }
    }
    printf("%d\n", res*res);
    return 0;
}