2021 Feb Silver Problem 1 Comfortable Cows
Official Problem Statement[edit]
Problem[edit]
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[edit]
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[edit]
C++[edit]
#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[edit]
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[edit]
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()