Comfortable Cows
Explicación
Nótese que en cualquier momento, si hay una vaca adyacente a exactamente otras tres vacas, el Granjero Nhoj debe colocar una vaca en el cuarto lugar que falta. El problema se convierte entonces en uno de flood fill (relleno), donde, después de añadir cada vaca adicional, hay que comprobar cuántas vacas más se añaden como resultado y sumarlas a la respuesta.
Podemos mantener un arreglo booleano 2D que representa si cada celda contiene una vaca y una cola que representa las coordenadas de las vacas nuevas que se van añadiendo.
En cada paso, añadimos la vaca en a nuestra cola. Mientras la cola no esté vacía, debemos extraer de la cola y comprobar si la vaca actual que se está añadiendo o alguno de sus vecinos tiene exactamente tres vacas adyacentes.
Si alguna de las celdas anteriores tiene exactamente vecinos adyacentes y no ha sido visitada ya, metemos las coordenadas de la cuarta celda adyacente que falta en la cola.
En cada paso, contamos el número total de celdas llenadas con un contador. Entonces, la cantidad de vacas adicionales necesarias sería el total de vacas menos la cantidad actual de vacas.
También es importante darse cuenta de que las coordenadas de las vacas adicionales pueden superar la grilla de 1000 por 1000 prevista para las vacas nuevas en hasta 500 en cada dirección. Por eso se puede hacer la grilla de 2000 por 2000.
Implementación
Complejidad temporal: , donde es el lado de la grilla.
#include <bits/stdc++.h>
using namespace std;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
/** @returns la cantidad de vecinos que rodean a una vaca específica de la grilla */
int count_neighbors(vector<vector<bool>> &v, int x, int y) {
int count_neighbors = 0;
for (int i = 0; i < 4; i++) {
if (v[x + dx[i]][y + dy[i]]) count_neighbors++;
}
return count_neighbors;
}
/** @returns la coordenada (x,y) de la cuarta casilla vacía de la grilla para cualquier vaca. */
array<int, 2> find_empty(vector<vector<bool>> &v, int x, int y) {
array<int, 2> empty_cell;
for (int i = 0; i < 4; i++) {
if (!v[x + dx[i]][y + dy[i]]) empty_cell = {x + dx[i], y + dy[i]};
}
return empty_cell;
}
/**
* Comprueba si una vaca tiene exactamente tres vecinos, y si la 4.ª celda
* no ha sido metida ya, la mete en la cola.
*/
void check_cell(int x, int y, vector<vector<bool>> &v, queue<array<int, 2>> &to_place) {
if (count_neighbors(v, x, y) == 3) {
array<int, 2> empty_cell = find_empty(v, x, y);
if (!v[empty_cell[0]][empty_cell[1]]) { to_place.push(empty_cell); }
}
}
int main() {
int n;
cin >> n;
vector<vector<bool>> filled(2000, vector<bool>(2000));
queue<array<int, 2>> to_place;
int total_cows = 0;
for (int cow_number = 1; cow_number <= n; cow_number++) {
array<int, 2> new_cow;
cin >> new_cow[0] >> new_cow[1];
// Desplazar las coordenadas de la grilla en 1000 para tener en cuenta la expansión
new_cow[0] += 500;
new_cow[1] += 500;
to_place.push(new_cow);
while (!to_place.empty()) {
// Obtener la vaca actual que estamos procesando de la cola y quitarla
array<int, 2> current_cow = to_place.front();
to_place.pop();
if (filled[current_cow[0]][current_cow[1]]) continue;
total_cows++;
filled[current_cow[0]][current_cow[1]] = true;
// Ahora comprobamos si la celda actual y todas las adyacentes se ven afectadas
check_cell(current_cow[0], current_cow[1], filled, to_place);
for (int i = 0; i < 4; i++) {
if (filled[current_cow[0] + dx[i]][current_cow[1] + dy[i]]) {
check_cell(current_cow[0] + dx[i], current_cow[1] + dy[i], filled,
to_place);
}
}
}
// La salida es el número de vacas menos la cantidad de vacas colocadas por Nhoj
cout << total_cows - cow_number << endl;
}
}import java.io.*;
import java.util.*;
public class ComfortableCows {
public static int[] dx = {1, 0, -1, 0};
public static int[] dy = {0, 1, 0, -1};
/** @returns la cantidad de vecinos que rodean a una vaca específica de la grilla */
public static int countNeighbors(boolean[][] v, int x, int y) {
int countNeighbors = 0;
for (int i = 0; i < 4; i++) {
if (v[x + dx[i]][y + dy[i]]) countNeighbors++;
}
return countNeighbors;
}
/** @returns la coordenada (x,y) de la cuarta casilla vacía de la grilla para cualquier vaca. */
public static int[] findEmpty(boolean[][] v, int x, int y) {
int[] emptyCell = new int[2];
for (int i = 0; i < 4; i++) {
if (!v[x + dx[i]][y + dy[i]]) {
emptyCell[0] = x + dx[i];
emptyCell[1] = y + dy[i];
}
}
return emptyCell;
}
/**
* Comprueba si una vaca tiene exactamente tres vecinos, y si la 4.ª celda
* no ha sido metida ya, la mete en la cola.
*/
public static void checkCell(int x, int y, boolean[][] v, Queue<int[]> toPlace) {
if (countNeighbors(v, x, y) == 3) {
int[] emptyCell = findEmpty(v, x, y);
if (!v[emptyCell[0]][emptyCell[1]]) { toPlace.add(emptyCell); }
}
}
public static void main(String[] args) throws IOException {
BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
PrintWriter output = new PrintWriter(System.out);
int n = Integer.parseInt(read.readLine());
Queue<int[]> toPlace = new ArrayDeque<>();
int totalCows = 0;
boolean[][] filled = new boolean[2000][2000];
for (int cowNum = 1; cowNum <= n; cowNum++) {
StringTokenizer coords = new StringTokenizer(read.readLine());
int x = Integer.parseInt(coords.nextToken()) + 500;
int y = Integer.parseInt(coords.nextToken()) + 500;
// Desplazar las coordenadas de la grilla en 1000 para tener en cuenta la expansión
int[] newCow = new int[2];
newCow[0] = x;
newCow[1] = y;
// Meter la nueva vaca en la cola
toPlace.add(newCow);
while (!toPlace.isEmpty()) {
int[] currentCow = toPlace.poll();
if (filled[currentCow[0]][currentCow[1]]) { continue; }
totalCows++;
filled[currentCow[0]][currentCow[1]] = true;
// Ahora comprobamos si la celda actual y todas las adyacentes se
// ven afectadas
checkCell(currentCow[0], currentCow[1], filled, toPlace);
for (int i = 0; i < 4; i++) {
if (filled[currentCow[0] + dx[i]][currentCow[1] + dy[i]]) {
checkCell(currentCow[0] + dx[i], currentCow[1] + dy[i], filled,
toPlace);
}
}
}
// La respuesta es el número total de vacas menos la cantidad de vacas
// colocadas específicamente por el granjero nhoj
output.println(totalCows - cowNum);
}
output.close();
}
}from collections import deque
from typing import List
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
def count_neighbors(v: List[List[bool]], x: int, y: int) -> int:
""":return: la cantidad de vecinos que rodean a una vaca específica de la grilla"""
count_neighbors = 0
for i in range(4):
if v[x + dx[i]][y + dy[i]]:
count_neighbors += 1
return count_neighbors
def find_empty(v: List[List[bool]], x: int, y: int) -> List[int]:
""":return: la coordenada (x,y) de la cuarta casilla vacía de la grilla para cualquier vaca."""
for i in range(4):
if not v[x + dx[i]][y + dy[i]]:
empty_cell = [x + dx[i], y + dy[i]]
return empty_cell
def check_cell(x: int, y: int, v: List[List[bool]], to_place: deque):
"""
Comprueba si una vaca tiene exactamente tres vecinos, y si la 4.ª
celda no ha sido metida ya, la mete en la cola.
"""
if count_neighbors(v, x, y) != 3:
return
empty_cell = find_empty(v, x, y)
if not v[empty_cell[0]][empty_cell[1]]:
to_place.append(empty_cell)
n = int(input())
to_place = deque()
filled = [[False] * 2000 for _ in range(2000)]
total_cows = 0
for cow_number in range(1, n + 1):
new_cow = list(map(int, input().split()))
new_cow[0] += 500
new_cow[1] += 500
# Desplazar las coordenadas de la grilla en 1000 para tener en cuenta la expansión
to_place.append(new_cow)
while to_place:
current_cow = to_place.popleft()
if filled[current_cow[0]][current_cow[1]]:
continue
total_cows += 1
filled[current_cow[0]][current_cow[1]] = True
# Ahora comprobamos si la celda actual y todas las adyacentes se ven afectadas
check_cell(current_cow[0], current_cow[1], filled, to_place)
for i in range(4):
if filled[current_cow[0] + dx[i]][current_cow[1] + dy[i]]:
check_cell(
current_cow[0] + dx[i], current_cow[1] + dy[i], filled, to_place
)
# La respuesta es el número total de vacas menos la cantidad de vacas colocadas específicamente por el granjero nhoj
print(total_cows - cow_number)