Skip to Content
CTRL K

Big Brush

Análisis oficial (C++) 

Explicación

Como en muchos problemas, el truco es empezar al revés.

Buscamos todas las regiones de 2 por 2 (en adelante, solo “regiones”) que podrían haberse pintado al final (posible si las cuatro casillas son del mismo color) y expandimos hacia afuera desde ellas.

Podemos hacer esto porque, después de “cubrir” algunas regiones iniciales, ahora podemos “meter” regiones adyacentes que no se pueden pintar tan fácilmente en las partes que ya estaban cubiertas.

Por ejemplo, consideremos esta área donde cubrimos primero la región central de 00s:

1111
1001
1001
1111

Después de hacer eso, ahora podemos cubrir los 11s pintándolos primero y luego pintando la región central con 00s.

Esa región de 00s solo afecta nuestra opinión del área de 4 por 4 circundante; ninguna otra parte del lienzo se ve afectada.

Solo hay 88 regiones más (sin contar la original que acabamos de pintar encima) que podrían haberse vuelto válidas al cubrir una, así que no hay demasiadas aristas que considerar.

Implementación

Las regiones se representan por el índice de su esquina superior izquierda.

Complejidad temporal: O(nm)\mathcal{O}(nm)

#include <algorithm>
#include <iostream>
#include <set>
#include <vector>
 
using std::cout;
using std::endl;
using std::pair;
using std::vector;
 
/** @return todas las nuevas regiones posibles que ahora podríamos pintar  */
vector<pair<int, int>> new_paints(int r, int c) {
	return {{r - 1, c - 1}, {r, c - 1},     {r + 1, c - 1}, {r - 1, c},
	        {r + 1, c},     {r - 1, c + 1}, {r, c + 1},     {r + 1, c + 1}};
}
 
int main() {
	int row_num, col_num;
	std::cin >> row_num >> col_num;
	vector<vector<int>> grid(row_num, vector<int>(col_num));
	for (int r = 0; r < row_num; r++) {
		for (int c = 0; c < col_num; c++) { std::cin >> grid[r][c]; }
	}
 
	// cada casilla que ya está pintada; podemos meter otras regiones en estas
	vector<vector<bool>> painted(row_num, vector<bool>(col_num));
	/** @return si una región se puede pintar, y el color con el que pintarla  */
	auto can_paint = [&](int r, int c) {
		if (!(0 <= r && r < row_num - 1 && 0 <= c && c < col_num - 1)) { return -1; }
		std::set<int> colors;
		if (!painted[r][c]) { colors.insert(grid[r][c]); }
		if (!painted[r + 1][c]) { colors.insert(grid[r + 1][c]); }
		if (!painted[r][c + 1]) { colors.insert(grid[r][c + 1]); }
		if (!painted[r + 1][c + 1]) { colors.insert(grid[r + 1][c + 1]); }
		return colors.size() == 1 ? *colors.begin() : -1;
	};
 
	vector<pair<int, int>> frontier;
	vector<vector<int>> ops;
	// hallar todas las regiones iniciales válidas
	for (int r = 0; r < row_num - 1; r++) {
		for (int c = 0; c < col_num - 1; c++) {
			int color = can_paint(r, c);
			if (color != -1) {
				frontier.push_back({r, c});
				painted[r][c] = painted[r + 1][c] = painted[r][c + 1] =
				    painted[r + 1][c + 1] = true;
				ops.push_back({r, c, color});
			}
		}
	}
	// expandir hacia afuera desde lo que encontramos
	while (!frontier.empty()) {
		const auto [r, c] = frontier.back();
		frontier.pop_back();
 
		for (const auto &[nr, nc] : new_paints(r, c)) {
			int color = can_paint(nr, nc);
			if (color != -1) {
				painted[nr][nc] = painted[nr + 1][nc] = painted[nr][nc + 1] =
				    painted[nr + 1][nc + 1] = true;
				ops.push_back({nr, nc, color});
				frontier.push_back({nr, nc});
			}
		}
	}
 
	// comprobar si se omitió alguna casilla y no se pudo pintar
	for (int r = 0; r < row_num; r++) {
		for (int c = 0; c < col_num; c++) {
			if (!painted[r][c]) {
				cout << -1 << endl;
				return 0;
			}
		}
	}
 
	cout << ops.size() << endl;
	for (int i = ops.size() - 1; i >= 0; i--) {
		printf("%i %i %i\n", ops[i][0] + 1, ops[i][1] + 1, ops[i][2]);
	}
}
Fundamentos