[editorial] Online Round 2 - C. Bacteria

  • Toivoa
    Toivoa

    2차원 평면 위에 살고 있는 박테리아는 세대가 지남에 따라 다음 특성을 보입니다.
    1. 어떤 위치에 박테리아가 살아있고, 왼쪽 혹은 위에 살아있는 박테리아가 있으면 다음 세대에도 박테리아가 살아남는다.
    2. 어떤 위치에 박테리아가 없고, 왼쪽과 위에 박테리아가 모두 살아 있다면 다음 세대에 박테리아가 생겨난다.
    두 조건을 만족하지 않는 경우는 다음 세대에 박테리아가 (죽거나) 나타나지 않습니다.

    문제는 박테리아의 정보가 주어졌을 때 몇 세대가 지나야 박테리아가 모두 없어지는지 알아내는 것입니다.

    small input은 좌표 공간의 크기가 작기 때문에 simulation을 해보셔도 됩니다. 여기에 대한 설명은 생략합니다.
    large input은 좌표 공간이 크기 때문에 simulation을 해서는 메모리 문제도 있고, 시간 내에 나올 수가 없습니다.
    다른 방법도 있을 수 있겠지만, 여기에서는 simulation과 유사하게 풀었습니다.
    1. 일단 plane sweeping을 이용해서 좌표 공간의 크기를 줄이고 박테리아들을 채워둡니다.
    2. 박테리아가 위치한 공간에서 바로 상하좌우에 박테리아가 있다면 이 박테리아들은 life time에 영향을 줍니다. 또한 박테리아의 위치에서 오른쪽 위, 혹은 왼쪽 아래에 있는 박테리아들도 life time에 영향을 줍니다. 설명이 어렵다면 그려서 시뮬레이션 해보세요!
    3. 2번에서 찾아낸 life time에 영향을 주는 박테리아들을 flood fill을 이용해서 한 집합으로 묶습니다.
    4. 각 집합에 대해서 최종적인 life time을 DP로 계산합니다. 여기에서 주의할 점은 입력에 따라 (영역이 확장되어감에 따라) 각 박테리아 집합의 영역이 겹치는 경우가 있는데 이를 영향을 주지 않도록 독립적으로 계산해야 한다는 것입니다.
    5. 한 집합에 대해 life time은 다음과 같이 계산합니다.
    a. 초기값: 해당 위치에 박테리아가 있는 경우에는 [(좌표 공간의 너비 + 높이) - 1]. 박테리아가 없는 경우에는 [0].
    b. 해당 위치에 박테리아가 있는 경우에는 다음 값들의 최대값.
    -> 왼쪽에 처음부터 박테리아가 있다면 왼쪽의 life time + 좌표 공간의 너비
    -> 위에 처음부터 박테리아가 있다면 위쪽의 life time + 좌표 공간의 높이.
    c. 박테리아의 유무에 상관 없이 현재 위치의 왼쪽과 위에 박테리아가 모두 존재할 수 있다면 (처음에는 없어도 중간에 생겨날 수 있다면) 다음 값들의 최대값이 됩니다.
    -> 왼쪽의 life time + 좌표 공간의 너비
    -> 위쪽의 life time + 좌표 공간의 높이.
    이렇게 계산하면서 나오는 최대의 life time이 답이 됩니다. :)

    #include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
struct rect
{
    int x1, y1, x2, y2;
};
vector<int> x, y;
rect r[1000];
int life[2][2000][2000];
int arr[6][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}, {1, -1}, {-1, 1}};
int main()
{
    int t, cases = 0;
    scanf("%d", &t);
    while(t--)
    {
        int res = 0;
        int R;
        fill(life[0][0], life[1][0], -1);
        scanf("%d", &R);
        for (int i = 0; i < R; ++i)
        {
            scanf("%d%d%d%d", &r[i].x1, &r[i].y1, &r[i].x2, &r[i].y2);
            r[i].x2++; r[i].y2++;
            x.push_back(r[i].x1);
            x.push_back(r[i].x2);
            y.push_back(r[i].y1);
            y.push_back(r[i].y2);
        }
        sort(x.begin(), x.end());
        sort(y.begin(), y.end());
        x.erase(unique(x.begin(), x.end()), x.end());
        y.erase(unique(y.begin(), y.end()), y.end());
        for (int i = 0; i < R; ++i)
        {
            int sx = lower_bound(x.begin(), x.end(), r[i].x1) - x.begin();
            int ex = lower_bound(x.begin(), x.end(), r[i].x2) - x.begin();
            int sy = lower_bound(y.begin(), y.end(), r[i].y1) - y.begin();
            int ey = lower_bound(y.begin(), y.end(), r[i].y2) - y.begin();
            for (int X = sx; X < ex; ++X)
                for (int Y = sy; Y < ey; ++Y)
                {
                    life[0][X][Y] = -2;
                }
        }
        int rects = 0;
        for (size_t i = 0; i < x.size(); ++i)
        {
            for (size_t j = 0; j < y.size(); ++j)
            {
                if (life[0][i][j] == -2)
                {
                    queue< pair<size_t, size_t> > q;
                    pair<size_t, size_t> c, d;
                    c.first = i; c.second = j;
                    life[0][i][j] = rects;
                    r[rects].x1 = r[rects].x2 = i; r[rects].y1 = r[rects].y2 = j;
                    q.push(c);
                    while (!q.empty())
                    {
                        c = q.front(); q.pop();
                        for (int k = 0; k < 6; ++k)
                        {
                            d.first = c.first + arr[k][0];
                            d.second = c.second + arr[k][1];
                            if (d.first < 0 || d.first >= x.size() || d.second < 0 || d.second >= y.size())
                                continue;
                            if (life[0][d.first][d.second] == -2)
                            {
                                life[0][d.first][d.second] = rects;
                                r[rects].x1 = min<size_t>(r[rects].x1, d.first);
                                r[rects].x2 = max<size_t>(r[rects].x2, d.first);
                                r[rects].y1 = min<size_t>(r[rects].y1, d.second);
                                r[rects].y2 = max<size_t>(r[rects].y2, d.second);
                                q.push(d);
                            }
                        }
                    }
                    ++rects;
                }
            }
        }
        for (int la = 0; la < rects; ++la)
        {
            fill(life[1][0], life[2][0], 0);
            for (int i = r[la].x1; i <= r[la].x2; ++i)
            {
                for (int j = r[la].y1; j <= r[la].y2; ++j)
                {
                    if (life[0][i][j] == la)
                    {
                        life[1][i][j] = (x[i + 1] - x[i]) + (y[j + 1] - y[j]) - 1;
                        int u = 0, l = 0;
                        if (i != 0 && life[0][i - 1][j] == la)
                            u = life[1][i - 1][j] + (x[i + 1] - x[i]);
                        if (j != 0 && life[0][i][j - 1] == la)
                            l = life[1][i][j - 1] + (y[j + 1] - y[j]);
                        life[1][i][j] = max(life[1][i][j], max(u, l));
                    }
                    if (i != 0 && j != 0)
                    {
                        const int &u = life[1][i - 1][j];
                        const int &l = life[1][i][j - 1];
                        if (u != 0 && l != 0)
                        {
                            life[1][i][j] = max(u + (x[i + 1] - x[i]), l + (y[j + 1] - y[j]));
                        }
                    }
                    res = max(res, life[1][i][j]);
                }
            }
        }
        printf("Case #%d: %d\n", ++cases, res);
        x.clear(); y.clear();
    }
}
    [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]

    14년 전
0개의 댓글이 있습니다.

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.