(Analysis by Benjamin Qi)

Whenever there exists a cow horizontally or vertically adjacent to three other cows, Farmer Nhoj is forced to place a cow at the fourth spot.

...    .C.
CCC -> CCC
.C.    .C.


So this is essentially a flood fill problem; while there exists a location that should contain a cow but does not, add a cow at that location.

My solution maintains a 2D boolean array of which locations currently contain cows, as well as a queue of locations in the pasture where a cow needs to be added. While the queue is nonempty, pop the top element $(x,y)$ of the queue and check whether a cow has already been added at $(x,y)$. If not, add the cow at $(x,y)$, and check whether any of the locations $(x,y),(x,y-1),(x,y+1),(x-1,y),(x+1,y)$ contain cows and are adjacent to exactly three cows. If so, add all such locations to the queue and repeat.

• The cows that will eventually be present on the pasture after the first $i$ cows are added is a superset of the cows that will eventually be present on the pasture after the first $i-1$ cows are added.

• This means that we don't need to reset the array between the addition of each cow.
• If all cells in $[0,1000]\times [0,1000]$ are initially occupied, Farmer Nhoj will need to add cows at all locations $(x,y)$ satisfying $x+y\ge 0,x+y\le 2000,x-y\le 1000,x-y\ge -1000$ (in other words, a diamond with vertices at $(-500,500), (500,-500), (1500,500),$ and $(500,1500)$). So if we increase the $x$ and $y$ cow locations by $500$, then all of these locations will lie in the range $[0,2000]\times [0,2000]$.
• In my solution, I use $1000$ instead of $500$.

Time Complexity: $\mathcal{O}(N+(\text{grid size})^2)$.

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

#define f first
#define s second

const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};

bool present[3000][3000]; // which locations contain cows

int main() {
int N; cin >> N;
queue<pair<int,int>> cows_to_place;
int total_cows = 0;
for (int initial_cows = 1; initial_cows <= N; ++initial_cows) {
pair<int,int> p; cin >> p.f >> p.s;
p.f += 1000, p.s += 1000;
cows_to_place.push(p);
auto re_evaluate = [&](int x, int y) {
// if cow adjacent to exactly three others
// add fourth location to queue
if (!present[x][y]) return;
for (int d = 0; d < 4; ++d)
for (int d = 0; d < 4; ++d) {
pair<int,int> nex{x+dx[d],y+dy[d]};
if (!present[nex.f][nex.s])
cows_to_place.push(nex);
}
};
while (!cows_to_place.empty()) {
pair<int,int> loc = cows_to_place.front();
cows_to_place.pop();
if (present[loc.f][loc.s]) continue;
++ total_cows; present[loc.f][loc.s] = 1;
re_evaluate(loc.f,loc.s);
for (int d = 0; d < 4; ++d)
re_evaluate(loc.f+dx[d],loc.s+dy[d]);
}
cout << total_cows-initial_cows << "\n";
}
}


Here is an alternative solution by Danny Mittal that does not use a queue:

import java.io.BufferedReader;
import java.io.IOException;
import java.util.StringTokenizer;

public class LonelyPastureSilver {
static final boolean[][] cows = new boolean[3000][3000];
static final int[][] adj = new int[3000][3000];

static void add(int x, int y) {
if (!cows[x][y]) {
cows[x][y] = true;
if (cows[x][y] && adj[x][y] == 3) {
for (int[] another : new int[][]{{x - 1, y}, {x + 1, y}, {x, y - 1}, {x, y + 1}}) {
int w = another[0];
int z = another[1];
}
}
for (int[] other : new int[][]{{x - 1, y}, {x + 1, y}, {x, y - 1}, {x, y + 1}}) {
int u = other[0];
int v = other[1];
if (cows[u][v] && adj[u][v] == 3) {
for (int[] another : new int[][]{{u - 1, v}, {u + 1, v}, {u, v - 1}, {u, v + 1}}) {
int w = another[0];
int z = another[1];
}
}
}
}
}

public static void main(String[] args) throws IOException {
StringBuilder out = new StringBuilder();