程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> UVA - 1493 Draw a Mess 並查集＋壓縮圖

UVA - 1493 Draw a Mess 並查集＋壓縮圖

編輯：C++入門知識

UVA - 1493 Draw a Mess 並查集＋壓縮圖

題目大意：給出n＊m的點，可以在上用不同顏色的筆畫矩形，菱形，等腰三角形和圓形，因為是一個一個畫的，所以有的點會被覆蓋掉，原先的顏色就會被覆蓋掉了。現在給出每個人畫的圖案和順序，問最後每種顏色占了多少個點

解題思路：如果直接暴力的話就會TLE
為了防止被覆蓋，就倒著畫，如果該點被占有了，就不可以再畫了
我們用並查集將每一個點所能到達的最右端的點紀錄下來，將那些被使用過的點並起來，然後依次從上往下掃

參考了學長的代碼。。。

#include
#include
#include
#include
#include
#include
#define maxn 210
#define maxm 50010
using namespace std;

int w[maxn][maxm], N, M, q; 
int color[10];
map Map;

struct Shape{
    int x, y, r, w, c, m, Start, End;

    void init() {
        if(m < 2) {
            Start = max(0,x - r);
            End = min(N - 1, x + r);
        }
        else{
            r  = (r + 1) / 2 - 1;
            Start = x;
            End = min(N - 1, r + x);
        }
    }
}S[maxm];

int find(int *f, int x) {
    return x == f[x] ? x : f[x] = find(f, f[x]);
}

void init() {
    for(int i = 0; i < N; i++)
        for(int j = 0; j <= M; j++) 
            w[i][j] = j;

    for(int i = 0; i < 10; i++)
        color[i] = 0;

    char str[20];

    for(int i = 0; i < q; i++) {
        scanf("%s", str);
        S[i].m =  Map[str[0]];
        if(str[0] != 'R') {
            scanf("%d%d%d%d",&S[i].x, &S[i].y, &S[i].r, &S[i].c);
            S[i].init();
        }
        else{
            scanf("%d%d%d%d%d", &S[i].x, &S[i].y, &S[i].r, &S[i].w, &S[i].c);
        }
    }
}

int count_Rec(int x, int y, int r, int W) {
    int cnt = 0;
    for(int i = x; i <= x + r - 1 && i < N; i++) {
        int t = y;
        while(t = find(w[i],t), abs(t - y) < W && t < M) {
            cnt++;
            w[i][t] = t + 1;
        }
    }
    return cnt;
}

int get_R(int x, int i, int r, int m) {

    if(m == 0)
        return (int)sqrt(1.0 * r * r - 1.0 * (x - i) * (x - i));
    else if(m == 1)
        return r - abs(x - i);
    else if(m == 2  )
        return r - (i - x);
    return 0;
}

int count_Oth(int x, int y, int r, int m, int Start, int End) {
    int cnt = 0;
    for(int i = Start; i <= End; i++) {
        int R = get_R(x, i, r, m);
        int t = max(0, y - R); 

        while(t = find(w[i], t) , abs(t - y) <= R && t < M) {
            cnt++;
            w[i][t] = t + 1;
        }
    }
    return cnt;
}

void solve() {
    for(int i = q - 1; i >= 0; i--) {
        int &col = color[S[i].c];
        if(S[i].m == 3)
            col += count_Rec(S[i].x, S[i].y, S[i].r, S[i].w);
        else
            col += count_Oth(S[i].x, S[i].y, S[i].r, S[i].m,S[i].Start, S[i].End);
    }

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

void begin() {
    Map['C'] = 0;
    Map['D'] = 1;
    Map['T'] = 2;
    Map['R'] = 3;
}

int main() {
    begin();
    while(scanf("%d%d%d", &N, &M, &q) != EOF) {
        init();
        solve();
    }
    return 0;
}