USACO 2021 February Contest Silver Division - Comfortable Cows

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

Based on the problem statement, what we want to do is just check for all cows that are adjacent to exactly three other cows and add a fourth one. This can be done using a queue.

Source code

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

#include <bits/stdc++.h>
using namespace std;

const int MAXX = 1000, MAXY = 1000, DIR = 4;

int wasVisited[5 * MAXX][5 * MAXY];

int dlin[DIR + 1] = {0, 0, 1, 0, -1};
int dcol[DIR + 1] = {0, 1, 0, -1, 0};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, i, x, y, lin, col, dir, d, numAdjacent, addedCows, l, c;
    pair<int, int> pos;
    queue<pair<int, int> > q;

    cin >> n;

    addedCows = 0;
    for (i = 0; i < n; i++) {
        cin >> x >> y;

        x += MAXX;
        y += MAXY;

        q.push({x, y});
        while (!q.empty()) {
            lin = q.front().first, col = q.front().second;
            q.pop();

            if (!wasVisited[lin][col]) {
                wasVisited[lin][col] = 1;
                addedCows++;
                for (dir = 0; dir < DIR + 1; dir++) {
                    l = lin + dlin[dir];
                    c = col + dcol[dir];

                    if (wasVisited[l][c]) {
                        // Counting the num of adjacent cows
                        numAdjacent = 0;
                        for (d = 1; d < DIR + 1; d++) {
                            if (wasVisited[l + dlin[d]][c + dcol[d]]) {
                                ++numAdjacent;
                            } else {
                                pos = {l + dlin[d], c + dcol[d]};
                            }
                        }

                        if (numAdjacent == 3) {  // If there are three adjacent cows
                            q.push(pos);         // Adding the fourth one
                        }
                    }
                }
            }
        }

        cout << addedCows - i - 1 << '\n';
    }

    return 0;
}