メモ

自分に向けて書いたメモを取り扱っています.

AOJ 0531 Paint Color

解法

座標圧縮→dfs(bfs)で領域を埋めていく
座標圧縮しないと、配列でベニヤ板の領域分取ることはできない

ソースコード

#define FOR(i, a, b) for (int i = (a);i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)

int w, h, n;
int X, Y;
bool field[1024][1024];

void mp(map<int, int>& a, vector<int>& b)
{
    sort(b.begin(), b.end());
    b.erase(unique(b.begin(), b.end()), b.end());

    REP(i, b.size())
        a[b[i]] = i;

    return;
}

void paint(int y, int x)
{
    field[y][x] = true;

    REP(i, 4)
    {
        int dx = x + DI[i], dy = y + DJ[i];
        if(0 <= dx && dx < X && 0 <= dy && dy < Y && !field[dy][dx])
        {
            paint(dy, dx);
        }
    }

    return;
}

int main()
{
    int x1[1024], y1[1024], x2[1024], y2[1024];

    while(~scanf("%d%d", &w, &h) && w)
    {
        memset(field, 0, sizeof field);
        int res = 0;
        vector<int> x, y;
        map<int, int> x_aft, y_aft;

        scanf("%d", &n);

        REP(i, n)
        {
            scanf("%d%d%d%d", x1+i, y1+i, x2+i, y2+i);
            x.push_back(x1[i]); x.push_back(x2[i]);
            y.push_back(y1[i]); y.push_back(y2[i]);
        }

        x.push_back(0); x.push_back(w);
        y.push_back(0); y.push_back(h);

        mp(x_aft, x);
        mp(y_aft, y);

        X = x.size();
        Y = y.size();

        REP(i,Y) REP(j,X)
            field[i][j] = (i == Y - 1 || j == X - 1);

        REP(i, n) FOR(j, y_aft[y1[i]], y_aft[y2[i]]) FOR(k, x_aft[x1[i]], x_aft[x2[i]])
            field[j][k] = true;

        REP(i, Y) REP(j, X)
            if(!field[i][j])
            {
                paint(i, j);
                res++;
            }

        printf("%d\n", res);
    }
}