UVA1493 - Draw a Mess(并查集)

题目链接

题目大意:一个N * M 的矩阵，每次你在上面将某个范围上色，不论上面有什么颜色都会被最新的颜色覆盖，颜色是1-9，初始的颜色是0.最后输出这个矩形中，每个颜色有多少个。某个范围这个分为了四种，圆，矩形，菱形，还有正三角形（倒着的）。注意这题的边界，不能超出这个矩形，很容易越界。

解题思路：因为题的矩阵范围是200 * 50000，然后操作又是50000，这样三个相乘，即使给60s也是不够的。因为行的数目比较少，如果每次都能将这一行哪个没处理过直接拿出来，而不用一个一个判断就快很多了，这样一来就相当于每个格子只要遍历一次。所以这里就每行用一个并查集，标记这这个位置以及后面的位置可以上色的起始位置。然后颜色更新问题只要将操作反着过来上色就可以处理了。

代码：

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>

using namespace std;
const int M = 50005;
const int N = 205;

int f[N][M];
int G[N][M];
int color[10];
int n, m, q;
char str[N];

struct OP {

    char type;
    int x, y, l, r, c;
}op[M];

int getParent (int x, int y) { 
    return y == f[x][y] ? y : f[x][y] = getParent (x, f[x][y]);
}

void init() {

    for (int i = q - 1; i >= 0; i--) {

        scanf ("%s", str);
        if (str[0] == ‘D‘)
            scanf ("%d%d%d%d", &op[i].x, &op[i].y, &op[i].l, &op[i].c);
        else if (str[0] == ‘T‘)
            scanf ("%d%d%d%d", &op[i].x, &op[i].y, &op[i].l, &op[i].c);
        else if (str[0] == ‘R‘)
            scanf ("%d%d%d%d%d", &op[i].x, &op[i].y, &op[i].l, &op[i].r, &op[i].c);
        else
            scanf ("%d%d%d%d", &op[i].x, &op[i].y, &op[i].l, &op[i].c);
        op[i].type = str[0];
    }

    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= m; j++)
            f[i][j] = j;
    memset (color, 0, sizeof (color));
}

void circle (int x, int y, int r, int c) {

    int L, R, s;
    for (int i = -r; i <= r; i++) {

        s = sqrt(r * r - i * i);  
        if (i + x >= n || i + x < 0)
            continue;
        L = max(y - s, 0);
        L = max (getParent (i + x, L), L);
        R = min (s + y, m - 1);

        for (int j = L; j <= R; j++) {
            if (j == getParent (i + x, j)) {
                color[c]++;
                f[i + x][j] = R + 1;    
            } else
                j = getParent(i + x, j) - 1;
        }
    }
}

void diamond (int x, int y, int r, int c) {

    int L, R;
    for (int i = -r; i <= r; i++) {

        if (i + x >= n || i + x < 0)
            continue;
        R = min (r - abs(i) + y, m - 1);
        L = max (abs(i) - r + y, 0);
        L = max (L, getParent (i + x, L));

        for (int j = L; j <= R; j++) {
            if (j == getParent (i + x, j)) {
                color[c]++;
                f[i + x][j] = R + 1;
            } else
                j = getParent (i + x, j) - 1;
        }
    }
}

void rectangle (int x, int y, int l, int w, int c) {

    int L, R;
    for (int i = x; i < min(x + l, n); i++) {

        L = max (y, getParent (i, y));
        R = min (y + w - 1, m - 1);

        for (int j = L; j <= R; j++) {
            if (j == getParent (i, j)) {
                color[c]++;
                f[i][j] = R + 1;
            } else
                j = getParent (i, j) - 1;
        }
    }
}

void triangle (int x, int y, int w, int c) {

    int L, R, h;
    h = (w + 1) / 2;
    for (int i = 0; i < h; i++) {

        if (i + x >= n)
            break;
        L = max (y - h + i + 1, 0);
        L = max (getParent(i + x, L), L);
        R = min (y + h - i - 1, m - 1);

        for (int j = L; j <= R; j++) {
             if (j == getParent (i + x, j)) {    
                color[c]++;
                f[i + x][j] = R + 1;
            } else
                j = getParent (i + x, j) - 1;
        }
    }
}

void solve () {

    for (int i = 0; i < q; i++) {

        if (op[i].type == ‘D‘)
            diamond (op[i].x, op[i].y, op[i].l, op[i].c);
        else if (op[i].type == ‘C‘)
            circle (op[i].x , op[i].y, op[i].l, op[i].c);
        else if (op[i].type == ‘T‘)
            triangle (op[i].x, op[i].y, op[i].l, op[i].c);
        else
            rectangle (op[i].x, op[i].y, op[i].l, op[i].r, op[i].c);
    }
}

int main () {

    char str[N];
    while (scanf ("%d%d%d", &n, &m, &q) != EOF) {

        init ();

        solve();

        for (int i = 1; i < 9; i++)
            printf ("%d ", color[i]);
        printf ("%d\n", color[9]);
    }
    return 0;
}

UVA1493 - Draw a Mess(并查集)