Build Gates

Explicación

Cada cerca puede pensarse como dos unidades de la grilla. Usamos dos por casos como $NESW$ . Si usáramos solo una unidad de grilla por cerca, no habría área adentro y por lo tanto subcontaríamos.

Podemos modelar las cercas y hacer flood fill para hallar el número de componentes conexas. La región no encerrada por una cerca también se cuenta como una componente conexa. Al fusionar las regiones encerradas por una cerca con la región no encerrada por la cerca, mediante una puerta, podemos asegurar que la granja quede conexa. Las vacas pueden ir de una región encerrada por una cerca a la región no encerrada por una cerca y luego visitar otra región encerrada por una cerca.

Por lo tanto, el número de puertas que hay que usar es igual al número de regiones encerradas por la cerca, que es el número de componentes conexas menos uno.

Podemos hacer flood fill y que las cercas indiquen un punto de parada. Si se ve una cerca, ya no continuamos el flood fill en esa dirección. Esto es porque el flood fill simula el movimiento de las vacas, y una vaca no puede atravesar una cerca.

Para contar el número de componentes conexas, hacemos flood fill desde cada punto dentro de nuestros límites (más sobre esto en la advertencia de abajo). Si ya visitamos un punto, no seguimos el flood fill. Si tenemos que empezar un flood fill nuevo, significa que el punto desde el que partimos no se alcanzó desde flood fills anteriores, o sea que está en una componente distinta. Así, sumamos uno a nuestro conteo de componentes conexas.

La solución oficial guarda la granja en un arreglo booleano de $2005 \times 2005$ con el origen en $(1002, 1002)$ , pero esto no es suficiente. Como cada segmento de cerca se duplica, la distancia máxima en cada dirección podría ser $2000$ unidades, lo que haría que una entrada como $1000$ $\texttt{N}$ s se salga de los límites.

Para no salirnos de los límites, hay que usar un arreglo de tamaño $4003 \times 4003$ : $1$ unidad para la posición del origen, $2000$ unidades en cada dirección desde el origen y $1$ unidad más en cada dirección para asegurar que la granja incluya área más allá de la cerca. El origen está en $(2001, 2001)$ , y hay espacio de “buffer” en la fila/columna $0$ y $4002$ , que se obtiene sumando o restando $2000$ al origen y luego sumando o restando $1$ correspondientemente.

Si hacemos flood fill por toda la grilla sin restricciones, ocurriría un desbordamiento de pila. Por eso debemos usar maxx, minx, maxy y miny.

Implementación

Complejidad temporal: $\mathcal{O}(N^2)$

C++Java


#include <cstdio>
#include <iostream>
#include <map>
using namespace std;
void ff(int i, int j);
 
bool fence[4003][4003] = {false};
bool visited[4003][4003] = {false};
int maxx = 2001, minx = 2001, maxy = 2001, miny = 2001;
int main() {
	freopen("gates.in", "r", stdin);
	freopen("gates.out", "w", stdout);
	int n;
	string path;
	cin >> n >> path;
	int x = 2001, y = 2001;
	map<char, pair<int, int>> dir{
	    {'N', {-1, 0}}, {'S', {1, 0}}, {'E', {0, 1}}, {'W', {0, -1}}};
	// marcamos las cercas, escalándolas para que ocupen 2 unidades en vez de 1
	for (int i = 0; i < n; i++) {
		fence[x + dir[path[i]].first][y + dir[path[i]].second] = true;
		fence[x + 2 * dir[path[i]].first][y + 2 * dir[path[i]].second] = true;
		x += 2 * dir[path[i]].first;
		y += 2 * dir[path[i]].second;
		minx = min(minx, x);
		maxx = max(maxx, x);
		miny = min(miny, y);
		maxy = max(maxy, y);
	}
	// expandimos la granja para incluir el área fuera de las cercas
	minx--;
	maxx++;
	miny--;
	maxy++;
	int regions = 0;
	// flood fill de la granja para hallar en cuántas regiones se divide
	for (int i = minx; i <= maxx; i++) {
		for (int j = miny; j <= maxy; j++) {
			if (!visited[i][j] && !fence[i][j]) {
				ff(i, j);
				regions++;
			}
		}
	}
	// la respuesta es regions - 1 porque cada puerta fusiona dos regiones
	cout << regions - 1 << endl;
	return 0;
}
 
void ff(int i, int j) {
	if (i < minx || i > maxx || j < miny || j > maxy || visited[i][j] || fence[i][j]) {
		return;
	}
	visited[i][j] = true;
	int x[] = {-1, 0, 0, 1}, y[] = {0, -1, 1, 0};
	for (int k = 0; k < 4; k++) { ff(i + x[k], j + y[k]); }
}


import java.io.*;
import java.util.*;
 
public class BuildGates {
	private static final Map<Character, int[]> DIR = new HashMap<>() {
		{
			put('N', new int[] {-1, 0});
			put('S', new int[] {1, 0});
			put('E', new int[] {0, 1});
			put('W', new int[] {0, -1});
		}
	};
 
	/*
	 * La mayor distancia que FJ puede recorrer desde el origen es 1000 unidades.
	 * Reservamos el doble (porque las posiciones pueden ser negativas)
	 * más 3 lugares extra para 0 y 1 unidad de padding de cada lado.
	 */
	private static final int MAX_POS = 1000;
	private static boolean[][] fence = new boolean[2 * MAX_POS + 3][2 * MAX_POS + 3];
	private static boolean[][] visited = new boolean[2 * MAX_POS + 3][2 * MAX_POS + 3];
 
	private static int min_x = Integer.MAX_VALUE;
	private static int max_x = Integer.MIN_VALUE;
	private static int min_y = Integer.MAX_VALUE;
	private static int max_y = Integer.MIN_VALUE;
 
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio("gates");
 
		int n = io.nextInt();
		String path = io.next();
 
		// desplazamos el origen
		int x = MAX_POS + 1;
		int y = MAX_POS + 1;
 
		// marcamos las cercas, escalándolas para que ocupen 2 unidades en vez de 1
		for (int i = 0; i < n; i++) {
			fence[x + DIR.get(path.charAt(i))[0]][y + DIR.get(path.charAt(i))[1]] =
			    true;
			fence[x + 2 * DIR.get(path.charAt(i))[0]]
			     [y + 2 * DIR.get(path.charAt(i))[1]] = true;
 
			x += 2 * DIR.get(path.charAt(i))[0];
			y += 2 * DIR.get(path.charAt(i))[1];
 
			min_x = Math.min(min_x, x);
			max_x = Math.max(max_x, x);
			min_y = Math.min(min_y, y);
			max_y = Math.max(max_y, y);
		}
 
		// expandimos la granja para incluir el área fuera de las cercas
		min_x--;
		max_x++;
		min_y--;
		max_y++;
 
		int regions = 0;
		for (int i = min_x; i <= max_x; i++) {
			for (int j = min_y; j <= max_y; j++) {
				if (!visited[i][j] && !fence[i][j]) {
					dfs(i, j);
					regions++;
				}
			}
		}
 
		// la respuesta es regions - 1 porque cada puerta fusiona dos regiones
		io.println(regions - 1);
		io.close();
	}
 
	private static void dfs(int startX, int startY) {
		Stack<int[]> stack = new Stack<>();
		stack.push(new int[] {startX, startY});
		visited[startX][startY] = true;
 
		int[] dx = {-1, 0, 0, 1};
		int[] dy = {0, -1, 1, 0};
 
		while (!stack.isEmpty()) {
			int[] curr = stack.pop();
			int x = curr[0];
			int y = curr[1];
 
			for (int k = 0; k < 4; k++) {
				int nx = x + dx[k];
				int ny = y + dy[k];
 
				if (nx >= min_x && nx <= max_x && ny >= min_y && ny <= max_y &&
				    !visited[nx][ny] && !fence[nx][ny]) {
					visited[nx][ny] = true;
					stack.push(new int[] {nx, ny});
				}
			}
		}
	}
 
	// CodeSnip{Kattio}
}

Solución alternativa más rápida

Es posible hacer las siguientes 2 observaciones:

Por cada región cerrada contigua debe haber 1 puerta. En un estado mínimo, cada región tiene exactamente 1 puerta. Por ejemplo, si hay 2 regiones, debe haber 2 puertas.
Cada vez que FJ llega a un nodo que ya visitó recorriendo una arista que no cruzó en ninguna dirección, crea exactamente 1 región nueva. En otras palabras, FJ crea exactamente 1 región cerrada contigua nueva si se cumplen todas estas condiciones:
- FJ camina por una arista del punto $a$ al $b$
- No caminó de $a$ a $b$ en el pasado
- No caminó de $b$ a $a$ en el pasado
- $b$ es un punto que ya había visitado

Bajo estas observaciones, podemos usar un conjunto de aristas visitadas y nodos visitados, y llevar la cuenta del número de regiones cerradas contiguas. Esta solución es unas 10 veces más rápida que el flood fill por las consultas e inserciones en $\log N$ .

Implementación

Complejidad temporal: $\mathcal{O}(N\log N)$

C++Python


#include <bits/stdc++.h>
using namespace std;
 
int main() {
	freopen("gates.in", "r", stdin);
	freopen("gates.out", "w", stdout);
 
	ios::sync_with_stdio(0);
	cin.tie(0);
 
	int n;
	cin >> n;
	string s;
	cin >> s;
 
	set<pair<pair<int, int>, pair<int, int>>> visedge;
	set<pair<int, int>> visnode;
	int ans = 0;
	pair<int, int> prev{0, 0};
	visnode.insert(prev);
 
	for (int i = 0; i < n; i++) {
		int x = prev.first;
		int y = prev.second;
		if (s[i] == 'N') {
			x++;
		} else if (s[i] == 'S') {
			x--;
		} else if (s[i] == 'E') {
			y--;
		} else {
			y++;
		}
 
		// Comprobamos si la arista de prev a {x, y} fue visitada (ver 2.ª
		// observación)
		if (visedge.find({{x, y}, prev}) == visedge.end() &&
		    visnode.find({x, y}) != visnode.end()) {
			ans++;
		}
 
		visedge.insert({{x, y}, prev});
		visedge.insert({prev, {x, y}});
		visnode.insert({x, y});
 
		prev.first = x;
		prev.second = y;
	}
	cout << ans << "\n";
}


with open("gates.in") as read:
	n = int(read.readline().strip())
	s = read.readline().strip()
 
visedge = set()
visnode = set()
 
prev = (0, 0)
visnode.add(prev)
ans = 0
for direction in s:
	x, y = prev
	if direction == "N":
		x += 1
	elif direction == "S":
		x -= 1
	elif direction == "E":
		y -= 1
	elif direction == "W":
		y += 1
 
	# Comprobamos si la arista de prev a {x, y} fue visitada (ver 2.ª observación)
	if ((x, y), prev) not in visedge and (x, y) in visnode:
		ans += 1
 
	visedge.add(((x, y), prev))
	visedge.add((prev, (x, y)))
	visnode.add((x, y))
 
	prev = (x, y)
 
print(ans, file=open("gates.out", "w"))