Puzzle de programación: ¿Cómo pintar un tablero?

Question

Hay una placa N x M que debemos pintar. Podemos pintar una fila completa o una columna completa a la vez. Dada una matriz de colores N x M de todas las celdas del tablero, encuentre la cantidad mínima de operaciones de pintura para pintar el tablero.

Por ejemplo: se debe pintar un tablero de 3 x 3, como sigue (R - rojo, B - azul, G - verde):

B, B, B
B, R, R
B , G, G

El número mínimo de operaciones de pintura es de 4:

• Paint fila 0 con Blue
• Paint fila 1 con Red
• pintura fila 2 con la columna de pintura
• Verde Azul 0 con

¿Cómo resolverlo?

Answer 1

Para empezar, puede intentar una búsqueda exhaustiva informada .

Deje que su gráfico de estados sea: G=(V,E) donde V = {all possible boards} y E = {(u,v) | you can move from board u to v within a single operation}.

• Tenga en cuenta que no es necesario para generar el gráfico de antemano - se puede generar sobre la marcha, utilizando una función successors(board), que devuelve todos los sucesores de la junta dado.

También necesitará h:V->R - un admissible heuristic function que evalúa la junta .

Ahora, puede ejecutar A*, o bi-directional búsqueda BFS [o combinación de ambos], su fuente será una pizarra blanca, y su objetivo es la placa solicitada. Debido a que usamos la función heurística admisible, A * es complete (siempre encuentra una solución, si existe) y optimal (encuentra la solución más corta), encontrará la mejor solución. [lo mismo vale para BFS bidireccional].

inconvenientes:

• Aunque el algoritmo se informó, que tendrán un comportamiento exponencial. Pero si es una pregunta de entrevista, creo que una solución no eficiente es mejor que ninguna solución.
• Aunque completo y óptimo, si no hay solución, el algoritmo puede quedar atrapado en un ciclo infinito o, como mínimo, un ciclo muy largo hasta que se dé cuenta de que ha exaltado todas las posibilidades.

(1) ejemplo para heurística admisible es h(board) = #(miscolored_squares)/max{m,n}

Answer 2

Esto parece un problema de diversión. Déjame intentarlo con algún pseudocódigo.

Function MinPaints(Matrix) Returns Integer 
    If the matrix is empty return 0 
    Find all rows and columns which have a single color 
    If there are none, return infinity, since there is no solution 
    Set the current minimum to infinity 
    For each row or column with single color: 
     Remove the row/column from the matrix 
     Call MinPaints with the new matrix 
     If the result is less than the current minimum, set the current minimum to the result 
    End loop 
    Return the current minimum + 1 
End Function 

Creo que va a resolver su problema, pero no intenté ninguna optimización ni nada. Sin embargo, esto puede no ser lo suficientemente rápido, no lo sé. Dudo que este problema se pueda resolver en un tiempo sub-exponencial.

Aquí es cómo este algoritmo se resolvería el ejemplo:

BBB 
BRR 
BGG 
| 
+---BRR 
| BGG 
| | 
| +---RR 
| | GG 
| | | 
| | +---GG 
| | | | 
| | | +---[] 
| | | | | 
| | | | Solvable in 0 
| | | | 
| | | Solvable in 1 
| | | 
| | +---RR 
| | | | 
| | | +---[] 
| | | | | 
| | | | Solvable in 0 
| | | | 
| | | Solvable in 1 
| | | 
| | Solvable in 2 
| | 
| Solvable in 3 
|      BB 
+---Another branch with RR ... 
|      GG 
Solvable in 4