Hatena::Grouptopcoder

qnighy[黄色]

2012-04-24

World Final 2011 - Ancient Messages

19:08 | はてなブックマーク - World Final 2011 - Ancient Messages - qnighy[黄色]

ACM-ICPC Live Archive

隣の誰かさんが解いていたので解いた。


#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

struct UF {
    vector<int> p;
    UF(int N) : p(N,-1) {}
    int rt(int x) { return p[x]<0?x:(p[x]=rt(p[x])); }
    bool eq(int x, int y) { return rt(x)==rt(y); }
    void cat(int x, int y) {
        x=rt(x); y=rt(y);
        if(x==y) return;
        if(p[x]<p[y]) swap(x,y);
        p[y]+=p[x];
        p[x]=y;
    }
};

int tbl[202][202];

int main() {
    for(int tci = 0; ; tci++) {
        int H,W; scanf("%d%d", &H, &W);
        if(H==0) break;
        for(int y = 0; y < 202; y++) fill(tbl[y],tbl[y]+202,0);
        for(int y = 0 ; y < H; y++) {
            for(int x = 0; x < W; x++) {
                int v; scanf("%1x", &v);
                tbl[y+1][x*4+1] = (v>>3)&1;
                tbl[y+1][x*4+2] = (v>>2)&1;
                tbl[y+1][x*4+3] = (v>>1)&1;
                tbl[y+1][x*4+4] = (v>>0)&1;
            }
        }
        H = H+2;
        W = W*4+2;
        UF uf1(W*H);
        for(int y = 0; y < H; y++) {
            for(int x = 0; x < W; x++) {
                if(0<y && tbl[y-1][x]==tbl[y][x]) uf1.cat((y-1)*W+x, y*W+x);
                if(0<x && tbl[y][x-1]==tbl[y][x]) uf1.cat(y*W+(x-1), y*W+x);
            }
        }
        UF uf2(W*H);
        for(int y = 0; y < H; y++) {
            for(int x = 0; x < W; x++) {
                if(0<y && !uf1.eq(0,(y-1)*W+x) && !uf1.eq(0,y*W+x)) uf2.cat((y-1)*W+x, y*W+x);
                if(0<x && !uf1.eq(0,y*W+(x-1)) && !uf1.eq(0,y*W+x)) uf2.cat(y*W+(x-1), y*W+x);
            }
        }
        static int cnt[40804];
        fill(cnt, cnt+W*H, 0);
        for(int y = 0; y < H; y++) {
            for(int x = 0; x < W; x++) {
                int p = y*W+x;
                int r1 = uf1.rt(p);
                int r2 = uf2.rt(p);
                if(r1==p && !uf1.eq(0,p)) {
                    cnt[r2]++;
                }
            }
        }
        static char str[50000];
        int str_siz = 0;
        for(int i = 0; i < W*H; i++) {
            if(cnt[i]) str[str_siz++] = "WAKJSD"[cnt[i]-1];
        }
        sort(str, str+str_siz);
        str[str_siz] = 0;
        printf("Case %d: %s\n", tci+1, str);
    }
    return 0;
}

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/qnighy/20120424