티스토리 뷰

알고리즘 관련/BOJ

BOJ)1460 진욱이의 농장

JASON 자손9319 2017. 9. 5. 01:36

문제: icpc.me/1460 


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


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


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


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


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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#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, 0sizeof(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;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)2337 트리 자르기  (1) 2017.09.05
BOJ)11003 최소값 찾기  (1) 2017.09.05
BOJ)1460 진욱이의 농장  (0) 2017.09.05
BOJ)13548 수열과 쿼리 6  (0) 2017.09.03
BOJ)2419 사수아탕  (0) 2017.08.27
BOJ)2370 시장 선거 포스터  (1) 2017.08.21
댓글
댓글쓰기 폼