Icy Perimeter

Explicación

Podemos usar BFS para explorar cada mancha, empezando desde un # no visitado. Durante el BFS, podemos calcular el área de la mancha contando el número de # visitados y determinar su perímetro analizando el entorno de cada #.

El perímetro se determina sumando el número de lados de todas las celdas que están adyacentes a un # o están en el borde.

Al recorrer la grilla, podemos iniciar un BFS para cada # no visitado para computar el área y el perímetro de todas las manchas. Dentro del BFS, para cada #, empezamos asumiendo que sus cuatro lados contribuyen al perímetro. Luego reducimos este conteo en uno por cada # vecino, ya que las aristas compartidas no suman al perímetro.

Implementación

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

C++JavaPython


#include <bits/stdc++.h>
using namespace std;
 
// Direcciones de movimiento (arriba, abajo, izquierda, derecha)
const vector<pair<int, int>> DIRECTIONS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
 
pair<int, int> bfs(int row, int col, const vector<vector<char>> &grid,
                   vector<vector<bool>> &visited) {
	const int n = grid.size();  // atajo
 
	queue<pair<int, int>> q;
	q.push({row, col});  // Empezamos BFS desde la celda dada (row, col)
 
	int area = 0;
	int perimeter = 0;
	while (!q.empty()) {
		auto [row, col] = q.front();  // Celda actual (row, col)
		q.pop();
 
		// Saltamos si la celda ya fue visitada
		if (visited[row][col]) { continue; }
 
		visited[row][col] = true;  // Marcamos la celda (row, col) como visitada
		area++;  // Incrementamos el área (cada '#' aporta 1 al área)
 
		// Cada celda empieza con 4 lados que contribuyen al perímetro
		int sides = 4;
		for (auto [dx, dy] : DIRECTIONS) {
			int next_row = row + dx;
			int next_col = col + dy;
 
			// Comprobamos si la celda vecina está dentro de la grilla
			if (next_row >= 0 && next_row < n && next_col >= 0 && next_col < n) {
				// Si el vecino (next_row, next_col) es parte de la misma mancha
				if (grid[next_row][next_col] == '#') {
					// Agregamos el vecino (next_row, next_col) a la cola
					q.push({next_row, next_col});
					sides--;  // Las aristas compartidas reducen la contribución al perímetro
				}
			}
		}
 
		perimeter += sides;  // Sumamos los lados restantes al perímetro
	}
 
	return {area, perimeter};
}
 
int main() {
	freopen("perimeter.in", "r", stdin);
	freopen("perimeter.out", "w", stdout);
 
	int n;
	cin >> n;
 
	vector<vector<char>> grid(n, vector<char>(n));
	vector<vector<bool>> visited(n, vector<bool>(n, false));
 
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) { cin >> grid[i][j]; }
	}
 
	int max_area = 0;
	int min_perimeter = INT_MAX;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (grid[i][j] != '#' || visited[i][j]) { continue; }
 
			const auto [area, perimeter] = bfs(i, j, grid, visited);
 
			// Actualizamos max_area y min_perimeter según los resultados del BFS
			if (area > max_area || (area == max_area && perimeter < min_perimeter)) {
				max_area = area;
				min_perimeter = perimeter;
			}
		}
	}
 
	cout << max_area << " " << min_perimeter << endl;
}


import java.io.*;
import java.util.*;
 
public class IcyPerimeter {
	// Direcciones de movimiento (arriba, abajo, izquierda, derecha)
	private static final int[][] DIRECTIONS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
 
	private static int[] bfs(int row, int col, char[][] grid, boolean[][] visited) {
		// Atajo para el tamaño de la grilla
		final int n = grid.length;
 
		Deque<int[]> q = new ArrayDeque<>();
		q.add(new int[] {row, col});  // Empezamos BFS desde la celda dada (row, col)
		int area = 0;
		int perimeter = 0;
		while (!q.isEmpty()) {
			int[] current = q.poll();  // Celda actual (row, col)
			row = current[0];
			col = current[1];
 
			// Saltamos si la celda ya fue visitada
			if (visited[row][col]) { continue; }
 
			visited[row][col] = true;  // Marcamos la celda (row, col) como visitada
			area++;  // Incrementamos el área (cada '#' aporta 1 al área)
 
			// Cada celda empieza con 4 lados que contribuyen al perímetro
			int sides = 4;
			for (int[] direction : DIRECTIONS) {
				int nextRow = row + direction[0];
				int nextCol = col + direction[1];
 
				// Comprobamos si la celda vecina está dentro de la grilla
				if (nextRow >= 0 && nextRow < n && nextCol >= 0 && nextCol < n) {
					// Si el vecino (nextRow, nextCol) es parte de la misma mancha
					if (grid[nextRow][nextCol] == '#') {
						// Agregamos el vecino (nextRow, nextCol) a la cola
						q.add(new int[] {nextRow, nextCol});
						sides--;  // Las aristas compartidas reducen la contribución al perímetro
					}
				}
			}
 
			perimeter += sides;  // Sumamos los lados restantes al perímetro
		}
 
		return new int[] {area, perimeter};
	}
 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new FileReader("perimeter.in"));
		int n = Integer.parseInt(br.readLine());
 
		char[][] grid = new char[n][n];
		boolean[][] visited = new boolean[n][n];
 
		for (int i = 0; i < n; i++) {
			String line = br.readLine();
			grid[i] = line.toCharArray();
		}
 
		int maxArea = 0;
		int minPerimeter = Integer.MAX_VALUE;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (grid[i][j] != '#' || visited[i][j]) { continue; }
 
				int[] result = bfs(i, j, grid, visited);
				int area = result[0];
				int perimeter = result[1];
 
				// Actualizamos maxArea y minPerimeter según los resultados del BFS
				if (area > maxArea || (area == maxArea && perimeter < minPerimeter)) {
					maxArea = area;
					minPerimeter = perimeter;
				}
			}
		}
 
		PrintWriter pw = new PrintWriter("perimeter.out");
		pw.println(maxArea + " " + minPerimeter);
		pw.close();
	}
}


from collections import deque
from typing import List, Tuple
 
# Direcciones de movimiento (arriba, abajo, izquierda, derecha)
DIRECTIONS = [(-1, 0), (1, 0), (0, -1), (0, 1)]
 
 
def bfs(
	row: int, col: int, grid: List[str], visited: List[List[bool]]
) -> Tuple[int, int]:
	# Atajo para el tamaño de la grilla
	n = len(grid)
 
	queue = deque()
	queue.append((row, col))  # Empezamos BFS desde la celda dada (row, col)
 
	area = 0
	perimeter = 0
 
	while queue:
		row, col = queue.popleft()  # Celda actual (row, col)
 
		# Saltamos si la celda ya fue visitada
		if visited[row][col]:
			continue
 
		visited[row][col] = True  # Marcamos la celda (row, col) como visitada
		area += 1  # Incrementamos el área (cada '#' aporta 1 al área)
 
		# Cada celda empieza con 4 lados que contribuyen al perímetro
		sides = 4
		for dx, dy in DIRECTIONS:
			next_row = row + dx
			next_col = col + dy
 
			# Comprobamos si la celda vecina está dentro de la grilla
			if 0 <= next_row < n and 0 <= next_col < n:
				# Si el vecino (next_row, next_col) es parte de la misma mancha
				if grid[next_row][next_col] == "#":
					# Agregamos el vecino (next_row, next_col) a la cola
					queue.append((next_row, next_col))
					sides -= 1  # Las aristas compartidas reducen la contribución al perímetro
 
		perimeter += sides  # Sumamos los lados restantes al perímetro
 
	return area, perimeter
 
 
with open("perimeter.in", "r") as fin:
	n = int(fin.readline().strip())
	grid = [fin.readline().strip() for _ in range(n)]
 
visited = [[False] * n for _ in range(n)]
 
max_area = 0
min_perimeter = float("inf")
for i in range(n):
	for j in range(n):
		if grid[i][j] != "#" or visited[i][j]:
			continue
 
		area, perimeter = bfs(i, j, grid, visited)
 
		# Actualizamos max_area y min_perimeter según los resultados del BFS
		if area > max_area or (area == max_area and perimeter < min_perimeter):
			max_area = area
			min_perimeter = perimeter
 
print(f"{max_area} {min_perimeter}", file=open("perimeter.out", "w"))