USACO 2018 December Contest Silver Division - Mooyo Mooyo

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

As the constraints are very small, we can run flood fill while we have components which respect the rule, being careful about casework so that we can remove the suitable components every time. We will keep running the algorithm until there are no more components which can be removed.

Source code

The source code in C++ can be seen below.

#include <bits/stdc++.h>
using namespace std;
ifstream f("mooyomooyo.in");
ofstream g("mooyomooyo.out");
int n, k;
bool viz[102][12];
int mat[102][12];
int lst[12];
char c[15];
int ox[] = {-1, 0, 1, 0};
int oy[] = {0, 1, 0, -1};
int lee(int L, int C) {
    viz[L][C] = 1;
    vector<pair<int, int> > v;
    v.push_back({L, C});
    deque<pair<int, int> > d;
    d.push_back({L, C});
    int ans = 1;
    while (!d.empty()) {
        int line = d[0].first;
        int column = d[0].second;
        d.pop_front();
        for (int i = 0; i <= 3; ++i) {
            int pr = line + ox[i];
            int cr = column + oy[i];
            if (pr == 0 || pr == n + 1 || cr == 0 || cr == 11) {
                continue;
            }
            if (mat[pr][cr] != mat[L][C]) {
                continue;
            }
            if (viz[pr][cr]) {
                continue;
            }
            ++ans;
            viz[pr][cr] = 1;
            v.push_back({pr, cr});
            d.push_back({pr, cr});
        }
    }
    if (ans >= k) {
        for (int i = 0; i < v.size(); ++i) {
            mat[v[i].first][v[i].second] = 0;
        }
    }
    return ans;
}
int main() {
    f >> n >> k;
    for (int i = 1; i <= n; ++i) {
        f >> c;
        for (int j = 0; j <= 9; ++j) {
            mat[i][j + 1] = (c[j] - '0');
        }
    }
    bool ok = 1;
    while (ok) {
        memset(viz, 0, sizeof(viz));
        for (int i = 1; i <= 10; ++i) {
            lst[i] = n;
        }
        ok = 0;
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= 10; ++j) {
                if (!mat[i][j]) {
                    continue;
                }
                if (viz[i][j]) {
                    continue;
                }
                int sz = lee(i, j);
                if (sz >= k) {
                    ok = 1;
                }
            }
        for (int i = n; i >= 1; --i)
            for (int j = 1; j <= 10; ++j)
                if (mat[i][j]) {
                    int val = mat[i][j];
                    mat[i][j] = 0;
                    mat[lst[j]][j] = val;
                    --lst[j];
                }
    }
    for (int i = 1; i <= n; g << '\n', ++i) {
        for (int j = 1; j <= 10; ++j) {
            g << mat[i][j];
        }
    }
    return 0;
}