4217번: 신성 문자

https://www.acmicpc.net/problem/4217


$O(chw)$

문자들은 구멍 개수로 구분하면 된다. flood fill을 이용해 풀어보자.

#include<stdio.h>
#include<string.h>
const int MAX_S = 2e2, fx[] = { 0,1,0,-1 }, fy[] = { 1,0,-1,0 };
int h, w, ck[MAX_S + 2][MAX_S + 2], res[200];
char p[] = { 'W','A','K','J','S','D' };
int ff(int x, int y, int c) {
    ck[x][y] = -1;
    int r = 0;
    for (int i = 0; i < 4; i++) {
        int tx = x + fx[i], ty = y + fy[i];
        if (tx<0 || tx>h + 1 || ty<0 || ty>w * 4 + 1) continue;
        if (ck[tx][ty] == 0) r += c, ff(tx, ty, 0);
        else if (ck[tx][ty] == 1 && c) r += ff(tx, ty, 1);
    }
    return r;
}
int main() {
    for (int c = 1;; c++) {
        scanf("%d %d", &h, &w);
        if (!h) break;
        memset(ck, 0, sizeof(ck));
        memset(res, 0, sizeof(res));
        for (int i = 1; i <= h; i++) {
            for (int j = 1, x; j <= w; j++) {
                scanf("%1x", &x);
                if (!x) continue;
                for (int k = 0; k < 4; k++) ck[i][j * 4 - k] = (x & 1 << k)>0;
            }
        }
        ff(0, 0, 0);
        printf("Case %d: ", c);
        for (int i = 1; i <= h; i++)
            for (int j = 1; j <= w * 4; j++)
                if (ck[i][j] == 1) res[p[ff(i, j, 1)]]++;
        for (int i = 'A'; i <= 'Z'; i++)
            for (int j = 0; j < res[i]; j++) printf("%c", i);
        puts("");
    }
    return 0;
}