2021 Feb Silver Problem 1 Comfortable Cows

Official Problem Statement

Comfortable Cows

Problem

In this problem, the term "comfortable" is defined for a cow if it is on a 2D grid and exactly 3 of its 4 adjacent cells (up, down, left, right) are occupied by other cows. An initially empty grid is given. Each time, a cow is added to an empty cell of the grid. We are to find out, after each cow is added, the total number of cows that are comfortable.

Solution

We will maintain a count of how many cows each cell needs to become comfortable, and a count of how many cows are currently comfortable. When we add a cow, it may cause nearby cells to become comfortable or uncomfortable, and we update our counts accordingly.

It's important to note that we need to count how many cows each cell needs, even if there is no cow there currently, since cows can be added later.

Code

C++

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

vector<vector<bool>> field(3000, vector<bool>(3000, false));
deque<pair<int, int>> queue;
struct Direction {int x; int y;};
vector<Direction> directions = { {0, 1}, {0, -1}, {1, 0}, {-1, 0} };
int addedCows, potentialCows;

void addPoint(pair<int, int> point);
void addCowFor(pair<int, int> point);

// Add cow and check if any point becomes potential cow position
void addCowFor(pair<int, int> point) {
    for (auto dir : directions) {
        if (!field[point.first + dir.x][point.second + dir.y]) {
            addPoint({point.first + dir.x, point.second + dir.y});
        }
    }
}

// Add potential cow position
void addPoint(pair<int, int> point) {
    field[point.first][point.second] = true;
    potentialCows++;
    int numOfCows = 0;
    for (auto dir : directions) {
        if (field[point.first + dir.x][point.second + dir.y]) {
            numOfCows++;
            queue.push_back({point.first + dir.x, point.second + dir.y});
        }
    }

    if (numOfCows == 3) {
        addCowFor(point);
    }
}

// Check and add potential cow positions
void check(pair<int, int> point) {
    addPoint(point);

    while(!queue.empty()) {
        pair<int, int> frontPoint = queue.front();
        queue.pop_front();
        int numOfCows = 0;
        for (auto dir : directions) {
            numOfCows += field[frontPoint.first + dir.x][frontPoint.second + dir.y];
        }
        
        if (numOfCows == 3) {
            addCowFor(frontPoint);
        }
    }
}

int main() {
    int numOfInputs; 
    cin >> numOfInputs;
    addedCows = 0; 
    potentialCows = 0;

    for (int i = 0; i < numOfInputs; i++) {
        pair<int, int> point;
        cin >> point.first >> point.second;
        point.first += 1000;
        point.second += 1000;
        if (field[point.first][point.second]) {
            potentialCows--;
        } else {
            addedCows++;
            check(point);
        }

        cout << (potentialCows - addedCows) << endl;
    }
}

Java

import java.util.*;
import java.io.*;

public class Main {
    static int N = 3000;
    static boolean[][] field = new boolean[N][N];
    static LinkedList<int[]> queue = new LinkedList<>();
    static int[][] directions = { {0, 1}, {0, -1}, {1, 0}, {-1, 0} };
    static int addedCows = 0, potentialCows = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int numOfInputs = Integer.parseInt(br.readLine());
        for (int i = 0; i < numOfInputs; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken()) + 1000;
            int y = Integer.parseInt(st.nextToken()) + 1000;

            if (field[x][y]) {
                potentialCows--;
            } else {
                addedCows++;
                check(new int[]{x, y});
            }

            System.out.println(potentialCows - addedCows);
        }
    }

    // Check and add potential cow positions
    static void check(int[] point) {
        addPoint(point);

        while (!queue.isEmpty()) {
            int[] frontPoint = queue.pollFirst();
            int numOfCows = 0;

            for (int[] dir : directions) {
                numOfCows += field[frontPoint[0] + dir[0]][frontPoint[1] + dir[1]] ? 1 : 0;
            }

            if (numOfCows == 3) {
                addCowFor(frontPoint);
            }
        }
    }

    // Add potential cow position
    static void addPoint(int[] point) {
        field[point[0]][point[1]] = true;
        potentialCows++;

        int numOfCows = 0;
        for (int[] dir : directions) {
            if (field[point[0] + dir[0]][point[1] + dir[1]]) {
                numOfCows++;
                queue.add(new int[] {point[0] + dir[0], point[1] + dir[1]});
            }
        }

        if (numOfCows == 3) {
            addCowFor(point);
        }
    }

    // Add cow and check if any point becomes potential cow position
    static void addCowFor(int[] point) {
        for (int[] dir : directions) {
            if (!field[point[0] + dir[0]][point[1] + dir[1]]) {
                addPoint(new int[]{point[0] + dir[0], point[1] + dir[1]});
            }
        }
    }
}

Python

import sys
from collections import deque

N = 3000
field = [[False]*N for _ in range(N)]
queue = deque()
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
added_cows = 0
potential_cows = 0


def add_point(point):
    global potential_cows
    field[point[0]][point[1]] = True
    potential_cows += 1
    num_of_cows = 0

    for dir in directions:
        if field[point[0] + dir[0]][point[1] + dir[1]]:
            num_of_cows += 1
            queue.append((point[0] + dir[0], point[1] + dir[1]))

    if num_of_cows == 3:
        add_cow_for(point)


def add_cow_for(point):
    for dir in directions:
        if not field[point[0] + dir[0]][point[1] + dir[1]]:
            add_point((point[0] + dir[0], point[1] + dir[1]))


def check(point):
    add_point(point)
    
    while queue:
        front_point = queue.popleft()
        num_of_cows = 0

        for dir in directions:
            if field[front_point[0] + dir[0]][front_point[1] + dir[1]]:
                num_of_cows += 1

        if num_of_cows == 3:
            add_cow_for(front_point)


def main():
    global added_cows, potential_cows
    n = int(sys.stdin.readline())
    for _ in range(n):
        x, y = map(int, sys.stdin.readline().split())
        x += 1000
        y += 1000

        if field[x][y]:
            potential_cows -= 1
        else:
            added_cows += 1
            check((x, y))

        print(potential_cows - added_cows)


if __name__ == "__main__":
    main()