Programmierung Puzzle: Wie ein Brett zu malen?

Question

Es gibt eine N x M Platine, die wir malen sollten. Wir können entweder eine ganze Zeile oder eine ganze Spalte gleichzeitig malen. Angesichts einer N x M Matrix von Farben aller Board-Zellen finden Sie die minimale Anzahl von Maloperationen, um die Platine zu malen.

Zum Beispiel: sollten wir malen eine 3 x 3 Board wie folgt (R - rot, B - blau, G - grün):

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

Die minimale Anzahl von Lackierarbeiten 4:

• Lack Zeile 0 mit Blue
• Lackreihe 1 mit Red
• Lackreihe 2 mit Green
• Lacksäule 0 mit Blue

Wie würden Sie es lösen?

Answer 1

Für den Anfang können Sie versuchen, eine informierte erschöpfende Suche.

Lassen Sie Ihre Staaten Grafik sein: wo V = {all possible boards} und E = {(u,v) | you can move from board u to v within a single operation}.

• Beachten Sie, dass Sie nicht brauchen, die Grafik im Voraus zu erzeugen - Sie können es on the fly erzeugen kann, mit einer successors(board) Funktion, die alle Nachfolger des gegebenen Bord zurückzukehren.

Sie müssen auch h:V->R - eine admissible heuristic function, die das Board auswertet.

Jetzt können Sie A* oder bi-directional BFS-Suche [oder Kombination von beiden] ausführen, Ihre Quelle wird eine weiße Tafel sein, und Ihr Ziel ist die angeforderte Platine. Da wir die zulässige heuristische Funktion verwenden - A * ist sowohl complete (findet immer eine Lösung, wenn eine existiert) und optimal (findet die kürzeste Lösung), wird es die beste Lösung finden. [Gleiches gilt für bidirektionales BFS].

Nachteile:

• Obwohl der Algorithmus informiert wird, wird es exponentielles Verhalten haben. Aber wenn es eine Interviewfrage ist, glaube ich, dass eine nicht effiziente Lösung besser als keine Lösung ist.
• Obwohl vollständig und optimal - wenn es keine Lösung gibt - kann der Algorithmus in einer Endlosschleife oder zumindest einer sehr langen Schleife stecken bleiben, bis er erkennt, dass er alle Möglichkeiten ausgeschöpft hat.

(1) Beispiel für zulässige Heuristik ist h(board) = #(miscolored_squares)/max{m,n}

Answer 2

Dieses wie ein Spaß Problem sieht. Lass es mich mit einem Pseudocode aufnehmen.

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 

Ich denke, das wird Ihr Problem lösen, aber ich habe keine Optimierung oder irgendetwas versucht. Das ist vielleicht nicht schnell genug, ich weiß es nicht. Ich bezweifle, dass dieses Problem in subexponentieller Zeit lösbar ist.

Hier ist, wie dieser Algorithmus das Beispiel lösen würde:

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