4217_신성문자

구현문제
나는 삼성 B형 연습중이었어서 dfs말고 bfs쓰고, queue도 직접 구현하였다.
디코딩하고 그림을 찾아내면 된다.
그림은 그 내부의 빈공간의 개수를 기준으로 찾으면 됨.

나는 일단 검은부분을 각각 idx를 올리면서 구해주고 - 각각의 그림은 다른 값을 갖게됨
다음으로 하얀부분에 들어가는데 그 하얀부분이 만나는 검은 부분의 값이 한 개일때 idx의 내부빈공간++을 해줌
그리고 counting sort로 출력~!
(외부로 나가는 건 또 따로 처리)

#include <iostream>
using namespace std;
 
struct pair2 {
    int y, x;
    pair2(int y = 0, int x = 0) : y(y), x(x) {}
};
 
class queue2 {
private:
    pair2 arr[100001];
    int l, r, cap;
public:
    queue2() {
        l = 0; r = 0; cap = 100000;
    }
    pair2 front() {
        if (l > r) return pair2();
        return arr[l];
    }
    void pop() {
        if (l == r) return; //empty
        l = (l + 1) % cap;
    }
    void push(int y, int x) {
        if ((r + 1) % cap == l) return; //overflow;
        arr[r].y = y; arr[r].x = x;
        r = (r + 1) % cap;
    }
    void clear() {
        l = r;
    }
    bool empty() {
        return l == r;
    }
};
 
//A - 1개 , J - 3개, D - 5개, S - 4개 , W - 0개 , K - 2개
int H, W, cnt;
char origin[201][51];
int visit[201][250], a[8] = { -1, 1, 0, 0, 0, 0, -1, 1 };
int words[25000], res[27], paint[250][250];
 
int bfs(int y, int x, int t) {
    if (t == 0) ++cnt;
    queue2 q;
    //queue<pair<int, int>> q;
    q.push( y, x );
    if (t == 0) visit[y][x] = cnt;
    else visit[y][x] = -2;
 
    int what = -1, count = 0;
    while (!q.empty()) {
        y = q.front().y;
        x = q.front().x; q.pop();
 
        for (int i = 0; i < 4; ++i) {
            int ny = y + a[i];
            int nx = x + a[i + 4];
            if (ny < 0 || nx < 0 || ny >= H || nx >= 4 * W) {
                if (what != -2) {
                    what = -2; count++;
                }
                continue;
            }
            if (paint[ny][nx] == 1 && !visit[ny][nx] && t == 0) {
                visit[ny][nx] = cnt;
                q.push(ny, nx);
            }
            if (paint[ny][nx] == 0 && !visit[ny][nx] && t == 1) {
                visit[ny][nx] = -2;
                q.push(ny, nx);
            }
            else if (paint[ny][nx] == 1 && t == 1) {
                if (what != visit[ny][nx]) {
                    what = visit[ny][nx];
                    count++;
                }
            }
        }
    }
 
    if (t == 1) {
        if (what > -1 && count == 1) {
            return what;
        }
        else return 0;
    }
 
    return 0;
}
 
int func(char c) {
    if (c >= '0' && c <= '9') return c - '0';
    if (c >= 'a' && c <= 'f') return c - 'a' + 10;
}
int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);
 
    int test = 0;
    while (1) {
        test++;
        cin >> H >> W;
        if (!H && !W) return 0;
        for (int i = 0; i < H; ++i) {
            for (int j = 0; j < 4*W; ++j) {
                visit[i][j] = 0;
            }
        }
 
        cnt = 0;
        for (int i = 0; i < H; ++i) cin >> origin[i];
 
        for (int i = 0; i < H; ++i) {
            for (int j = 0; j < W; ++j) {
                int tmp = func(origin[i][j]);
                for (int k = 3; k >= 0; --k) {
                    paint[i][j * 4 + k] = tmp % 2; tmp /= 2;
                }
            }
        }
 
        for (int i = 0; i < H; ++i) {
            for (int j = 0; j < W*4; ++j) {
                if (paint[i][j] == 1 && !visit[i][j]) {
                    bfs(i, j, 0);
                }
            }
        }
 
        for (int i = 0; i < H; ++i) {
            for (int j = 0; j < W * 4; ++j) {
                if (paint[i][j] == 0 && !visit[i][j]) {
                    int tmp = bfs(i, j, 1);
                    if (tmp != 0) {
                        words[tmp]++;
                    }
                }
            }
        }
 
        for (int i = 1; i <= cnt; ++i) {
            if (words[i] == 1) res[0]++;
            else if (words[i] == 3) res['J' - 'A']++;
            else if (words[i] == 5) res['D' - 'A']++;
            else if (words[i] == 4) res['S' - 'A']++;
            else if (words[i] == 0) res['W' - 'A']++;
            else if (words[i] == 2) res['K' - 'A']++;
            words[i] = 0;
        }
        cout << "Case " << test << ": ";
        for (int i = 0; i < 26; ++i) {
            for (int j = 0; j < res[i]; ++j){
                cout << (char)(i + 'A');
            }
            res[i] = 0;
        }
        cout << '\n';
 
    }
 
 
}