Skip to Content
CTRL K

Flood Fill

Análisis oficial (C++) 

Explicación

Sin preocuparnos por la corrección real, armemos lo que parece un estado de DP intuitivo. Sea \texttt{min\\_ops}[s][e] el número mínimo de operaciones que toma hacer que todos los números de ss a ee inclusive sean iguales. Para las transiciones, podemos venir de \texttt{min\\_ops}[s][e-1] o de \texttt{min\\_ops}[s+1][e]. También hay un caso en que los números en ss y ee son iguales, en cuyo caso podemos transicionar desde \texttt{min\\_ops}[s+1][e-1].

El problema de este planteo es que, bueno, está mal. Sin embargo, podemos hacerlo correcto con algunas observaciones sobre por qué da la respuesta incorrecta. Tomemos el primer caso de ejemplo:

5 2 2 1

\texttt{min\\_ops}[1][2] debería ser igual a 00, pero nuestras transiciones lo ponen en 11. La razón es que nuestro algoritmo no detecta elementos que ya son iguales y no necesitan fusionarse más. Este fenómeno se observa más claramente si se meten, por ejemplo, 10 números, todos iguales.

Una observación clave para combatir esto es que podemos tratar rangos de números idénticos consecutivos como un solo número. De esta forma, podemos garantizar que cada elemento es distinto de sus vecinos, y que no existen componentes preconectadas.

Después de este paso de preprocesamiento, nuestra definición de DP ahora es válida.

Implementación

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

#include <algorithm>
#include <iostream>
#include <vector>
 
using std::cout;
using std::endl;
using std::vector;
 
int main() {
	int len;
	std::cin >> len;
	vector<int> arr;
	for (int i = 0; i < len; i++) {
		int x;
		std::cin >> x;
		if (arr.empty() || x != arr.back()) { arr.push_back(x); }
	}
	len = arr.size();
 
	vector<vector<int>> min_ops(len, vector<int>(len));
	for (int l = 2; l <= len; l++) {
		for (int start = 0; start + l - 1 < len; start++) {
			int end = start + l - 1;
			min_ops[start][end] =
			    std::min(min_ops[start + 1][end], min_ops[start][end - 1]) + 1;
			if (arr[start] == arr[end] && l > 2) {
				min_ops[start][end] =
				    std::min(min_ops[start][end], min_ops[start + 1][end - 1] + 1);
			}
		}
	}
 
	cout << min_ops[0][len - 1] << endl;
}
import java.io.*;
import java.util.*;
 
public class FloodFill {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		int len = Integer.parseInt(read.readLine());
		List<Integer> arr = new ArrayList<>();
		StringTokenizer arrST = new StringTokenizer(read.readLine());
		for (int i = 0; i < len; i++) {
			int x = Integer.parseInt(arrST.nextToken());
			if (arr.isEmpty() || x != arr.get(arr.size() - 1)) { arr.add(x); }
		}
		len = arr.size();
 
		int[][] minOps = new int[len][len];
		for (int l = 2; l <= len; l++) {
			for (int start = 0; start + l - 1 < len; start++) {
				int end = start + l - 1;
				minOps[start][end] =
				    Math.min(minOps[start + 1][end], minOps[start][end - 1]) + 1;
 
				if (arr.get(start).equals(arr.get(end)) && l > 2) {
					minOps[start][end] =
					    Math.min(minOps[start][end], minOps[start + 1][end - 1] + 1);
				}
			}
		}
 
		System.out.println(minOps[0][len - 1]);
	}
}
from itertools import groupby
 
len_ = int(input())
arr = [int(i) for i in input().split()]
arr = [v for v, _ in groupby(arr)]
len_ = len(arr)
 
min_ops = [[0 for _ in range(len_)] for _ in range(len_)]
for l in range(2, len_ + 1):
	for start in range(len_ - l + 1):
		end = start + l - 1
		min_ops[start][end] = min(min_ops[start + 1][end], min_ops[start][end - 1]) + 1
		if arr[start] == arr[end] and l > 2:
			min_ops[start][end] = min(
				min_ops[start][end], min_ops[start + 1][end - 1] + 1
			)
 
print(min_ops[0][len_ - 1])
Fundamentos