Mooyo Mooyo

#include <bits/stdc++.h>
using namespace std;
 
const int MAX_COLS = 10;
// Direcciones de movimiento (arriba, abajo, izquierda, derecha)
const vector<pair<int, int>> MOVES = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
 
vector<pair<int, int>> find_region(const vector<string> &grid, int row, int col) {
	const int n = grid.size();          // Atajo para el número de filas
	const char color = grid[row][col];  // Color de la celda inicial
 
	queue<pair<int, int>> q;
	q.push({row, col});  // Empezamos BFS desde la celda dada (row, col)
 
	vector<pair<int, int>> cells;  // Guarda coordenadas de celdas conexas
	vector<vector<bool>> visited(n, vector<bool>(MAX_COLS, false));
	while (!q.empty()) {
		const 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;
		cells.push_back({row, col});  // Agregamos la celda a la región conexa
 
		for (auto [dx, dy] : MOVES) {
			int next_row = row + dx;
			int next_col = col + dy;
 
			// Comprobamos si la celda vecina está dentro de los límites
			if (next_row >= 0 && next_row < n && next_col >= 0 && next_col < MAX_COLS) {
				// Si el vecino (next_row, next_col) tiene el mismo color
				if (grid[next_row][next_col] == color) {
					// Agregamos el vecino (next_row, next_col) a la cola
					q.push({next_row, next_col});
				}
			}
		}
	}
 
	return cells;
}
 
vector<vector<pair<int, int>>> find_removable_regions(const vector<string> &grid,
                                                      int k) {
	const int n = grid.size();
	vector<vector<pair<int, int>>> removable_regions;
	vector<vector<bool>> visited(n, vector<bool>(MAX_COLS, false));
 
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < MAX_COLS; j++) {
			// Saltamos celdas ya visitadas o vacías ('0')
			if (grid[i][j] == '0' || visited[i][j]) { continue; }
 
			char color = grid[i][j];
			const auto cells = find_region(grid, i, j);
 
			// Marcamos todas las celdas de la región como visitadas
			for (auto [r, c] : cells) { visited[r][c] = true; }
 
			// Si el tamaño de la región alcanza el umbral, la agregamos a las regiones eliminables
			if (cells.size() >= k) { removable_regions.push_back(cells); }
		}
	}
 
	return removable_regions;
}
 
void apply_gravity(vector<string> &grid) {
	const int n = grid.size();
	for (int j = 0; j < MAX_COLS; j++) {
		int empty_row = n - 1;  // Empezamos desde el fondo de la columna
 
		// Movemos celdas no vacías a la posición más baja disponible de la columna
		for (int i = n - 1; i >= 0; i--) {
			if (grid[i][j] != '0') {
				swap(grid[empty_row][j], grid[i][j]);
				empty_row--;
			}
		}
	}
}
 
int main() {
	ifstream fin("mooyomooyo.in");
	int n, k;
	fin >> n >> k;
 
	vector<string> grid(n);
	for (int i = 0; i < n; i++) { fin >> grid[i]; }
 
	while (true) {
		// Hallamos todas las regiones eliminables (regiones de tamaño >= k)
		auto removable_regions = find_removable_regions(grid, k);
 
		if (removable_regions.empty()) { break; }
 
		// Eliminamos todas las regiones identificadas poniendo sus celdas en '0'
		for (const auto &region : removable_regions) {
			for (const auto &[row, col] : region) { grid[row][col] = '0'; }
		}
 
		// Aplicamos gravedad a la grilla
		apply_gravity(grid);
	}
 
	ofstream fout("mooyomooyo.out");
	for (const auto &row : grid) { fout << row << "\n"; }
}

import java.io.*;
import java.util.*;
 
public class MooyoMooyo {
	static final int MAX_COLS = 10;
	// Direcciones de movimiento
	static final int[][] MOVES = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
 
	static List<int[]> findRegion(char[][] grid, int row, int col) {
		int n = grid.length;          // Número de filas
		char color = grid[row][col];  // Color de la celda inicial
 
		ArrayDeque<int[]> queue = new ArrayDeque<>();
		queue.add(new int[] {row, col});  // Empezamos BFS desde la celda dada (row, col)
 
		List<int[]> cells = new ArrayList<>();  // Guarda coordenadas de celdas conexas
		boolean[][] visited = new boolean[n][MAX_COLS];
		while (!queue.isEmpty()) {
			int[] cell = queue.poll();
			int currentRow = cell[0], currentCol = cell[1];
 
			// Saltamos si la celda ya fue visitada
			if (visited[currentRow][currentCol]) { continue; }
 
			visited[currentRow][currentCol] = true;
			cells.add(cell);  // Agregamos la celda a la región conexa
 
			for (int[] move : MOVES) {
				int nextRow = currentRow + move[0];
				int nextCol = currentCol + move[1];
 
				// Comprobamos si la celda vecina está dentro de los límites
				if (nextRow >= 0 && nextRow < n && nextCol >= 0 && nextCol < MAX_COLS) {
					// Si el vecino (nextRow, nextCol) tiene el mismo color
					if (grid[nextRow][nextCol] == color) {
						// Agregamos el vecino (nextRow, nextCol) a la cola
						queue.add(new int[] {nextRow, nextCol});
					}
				}
			}
		}
 
		return cells;
	}
 
	static List<List<int[]>> findRemovableRegions(char[][] grid, int k) {
		int n = grid.length;
		List<List<int[]>> removableRegions = new ArrayList<>();
		boolean[][] visited = new boolean[n][MAX_COLS];
 
		for (int row = 0; row < n; row++) {
			for (int col = 0; col < MAX_COLS; col++) {
				// Saltamos celdas ya visitadas o vacías ('0')
				if (grid[row][col] == '0' || visited[row][col]) { continue; }
 
				char color = grid[row][col];
				List<int[]> cells = findRegion(grid, row, col);
 
				// Marcamos todas las celdas de la región como visitadas
				for (int[] cell : cells) { visited[cell[0]][cell[1]] = true; }
 
				// Si el tamaño de la región alcanza el umbral, la agregamos a las regiones
				// eliminables
				if (cells.size() >= k) { removableRegions.add(cells); }
			}
		}
 
		return removableRegions;
	}
 
	static void applyGravity(char[][] grid) {
		int n = grid.length;
		for (int col = 0; col < MAX_COLS; col++) {
			int emptyRow = n - 1;  // Empezamos desde el fondo de la columna
 
			// Movemos celdas no vacías a la posición más baja disponible de la columna
			for (int row = n - 1; row >= 0; row--) {
				if (grid[row][col] != '0') {
					char temp = grid[emptyRow][col];
					grid[emptyRow][col] = grid[row][col];
					grid[row][col] = temp;
					emptyRow--;
				}
			}
		}
	}
 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new FileReader("mooyomooyo.in"));
		PrintWriter pw = new PrintWriter(new FileWriter("mooyomooyo.out"));
 
		String[] firstLine = br.readLine().split(" ");
		int n = Integer.parseInt(firstLine[0]);
		int k = Integer.parseInt(firstLine[1]);
 
		char[][] grid = new char[n][MAX_COLS];
		for (int row = 0; row < n; row++) { grid[row] = br.readLine().toCharArray(); }
 
		while (true) {
			// Hallamos todas las regiones eliminables (regiones de tamaño >= k)
			List<List<int[]>> removableRegions = findRemovableRegions(grid, k);
 
			if (removableRegions.isEmpty()) { break; }
 
			// Eliminamos todas las regiones identificadas poniendo sus celdas en '0'
			for (List<int[]> region : removableRegions) {
				for (int[] cell : region) { grid[cell[0]][cell[1]] = '0'; }
			}
 
			// Aplicamos gravedad a la grilla
			applyGravity(grid);
		}
 
		for (char[] row : grid) { pw.println(new String(row)); }
 
		br.close();
		pw.close();
	}
}

from collections import deque
from typing import List, Tuple
 
MAX_COLS = 10
# Direcciones de movimiento (arriba, abajo, izquierda, derecha)
MOVES = [
	(1, 0),
	(-1, 0),
	(0, 1),
	(0, -1),
]
 
 
def find_region(grid: List[List[str]], row: int, col: int) -> List[Tuple[int, int]]:
	n = len(grid)  # Número de filas
	color = grid[row][col]  # Color de la celda inicial
 
	q = deque()
	q.append((row, col))  # Empezamos BFS desde la celda dada (row, col)
 
	cells = []  # Guarda coordenadas de celdas conexas
	visited = [[False] * MAX_COLS for _ in range(n)]
 
	while q:
		row, col = q.popleft()  # Celda actual (row, col)
 
		# Saltamos si la celda ya fue visitada
		if visited[row][col]:
			continue
 
		visited[row][col] = True
		cells.append((row, col))  # Agregamos la celda a la región conexa
 
		for dx, dy in MOVES:
			next_row = row + dx
			next_col = col + dy
 
			# Comprobamos si la celda vecina está dentro de los límites
			if 0 <= next_row < n and 0 <= next_col < MAX_COLS:
				# Si el vecino (next_row, next_col) tiene el mismo color
				if grid[next_row][next_col] == color:
					# Agregamos el vecino (next_row, next_col) a la cola
					q.append((next_row, next_col))
 
	return cells
 
 
def find_removable_regions(
	grid: List[List[str]], k: int
) -> List[List[Tuple[int, int]]]:
	n = len(grid)
	removable_regions = []
	visited = [[False] * MAX_COLS for _ in range(n)]
 
	for row in range(n):
		for col in range(MAX_COLS):
			# Saltamos celdas ya visitadas o vacías ('0')
			if grid[row][col] == "0" or visited[row][col]:
				continue
 
			color = grid[row][col]
			cells = find_region(grid, row, col)
 
			# Marcamos todas las celdas de la región como visitadas
			for r, c in cells:
				visited[r][c] = True
 
			# Si el tamaño de la región alcanza el umbral, la agregamos a las regiones eliminables
			if len(cells) >= k:
				removable_regions.append(cells)
 
	return removable_regions
 
 
def apply_gravity(grid: List[List[str]]) -> None:
	n = len(grid)
	for col in range(MAX_COLS):
		empty_row = n - 1  # Empezamos desde el fondo de la columna
 
		# Movemos celdas no vacías a la posición más baja disponible de la columna
		for row in range(n - 1, -1, -1):
			if grid[row][col] != "0":
				grid[empty_row][col], grid[row][col] = (
					grid[row][col],
					grid[empty_row][col],
				)
				empty_row -= 1
 
 
with open("mooyomooyo.in", "r") as fin:
	n, k = map(int, fin.readline().split())
	grid = [list(fin.readline().strip()) for _ in range(n)]
 
while True:
	# Hallamos todas las regiones eliminables (regiones de tamaño >= k)
	removable_regions = find_removable_regions(grid, k)
 
	if not removable_regions:
		break
 
	# Eliminamos todas las regiones identificadas poniendo sus celdas en '0'
	for region in removable_regions:
		for row, col in region:
			grid[row][col] = "0"
 
	# Aplicamos gravedad a la grilla
	apply_gravity(grid)
 
with open("mooyomooyo.out", "w") as fout:
	for row in grid:
		fout.write("".join(row) + "\n")