[BOJ] 16768 Mooyo Mooyo

문제

16768번: Mooyo Mooyo

With plenty of free time on their hands (or rather, hooves), the cows on Farmer John's farm often pass the time by playing video games. One of their favorites is based on a popular human video game called Puyo Puyo; the cow version is of course called Mooyo Mooyo.

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

풀이

코드

#include <cstdio>
#include <cstring>
#include <queue>
#include <deque>
using namespace std;
int dy[] = {0, 1, 0, -1}, dx[] = {-1, 0, 1, 0};
struct axis { int x, y; };
 
int n, k;
deque<int> dq[10];
int vis[10][100];
int ans[100][10];
 
int isK(int ix, int iy) {
    int ret = 1, color = dq[ix][iy];
    memset(vis, 0, sizeof(vis));
    queue<axis> q;
    vis[ix][iy] = 1;
    q.push({ix, iy});
    while (!q.empty()) {
        axis t = q.front(); q.pop();
        for(int i = 0; i < 4; i++) {
            int x = t.x + dx[i], y = t.y + dy[i];
            if (x < 0 or y < 0 or x >= 10 or y >= n) continue;
            if (vis[x][y] or color != dq[x][y]) continue;
            vis[x][y] = 1;
            ret++;
            q.push({x, y});
        }
    }
    return (ret >= k) ? 1 : 0;
}
 
void toZero(int ix, int iy) {
    int color = dq[ix][iy];
    memset(vis, 0, sizeof(vis));
    queue<axis> q;
    vis[ix][iy] = 1;
    dq[ix][iy] = 0;
    q.push({ix, iy});
 
    while (!q.empty()) {
        axis t = q.front(); q.pop();
        for(int i = 0; i < 4; i++) {
            int x = t.x + dx[i], y = t.y + dy[i];
            if (x < 0 or y < 0 or x >= 10 or y >= n) continue;
            if (vis[x][y] or color != dq[x][y]) continue;
            vis[x][y] = 1;
            dq[x][y] = 0;
            q.push({x, y});
        }
    }
}
 
void gravity() {
    for(int i = 0; i < 10; i++) {
        int cnt = 0;
        for(int j = 0; j < n; j++) {
            int t = dq[i].back();
            dq[i].pop_back();
            if (t == 0) cnt++;
            else dq[i].push_front(t);
        }
        for(int j = 0; j < cnt; j++) dq[i].push_front(0);
    }
}
 
int main() {
    scanf("%d %d", &n, &k);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < 10; j++) {
            scanf("%1d", &ans[i][j]);
        }
    }
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < 10; j++) {
            dq[j].push_back(ans[i][j]);
        }
    }
 
    while (1) {
        int isB = 1;
        for(int i = 0; i < 10; i++) {
            for(int j = 0; j < n; j++) {
                if (dq[i][j] == 0) continue;
                if (isK(i, j)) {
                    isB = 0;
                    toZero(i, j);
                }
            }
        }
        if (isB) break;
        gravity();
    }
 
    for(int j = 0; j < n; j++) {
        for(int i = 0; i < 10; i++) {
            printf("%d", dq[i][j]);
        }
        printf("\n");
    }
}