Programowanie Puzzle: Jak pomalować planszę?

Question

Jest tablica N x M, którą powinniśmy pomalować. Możemy malować jednocześnie cały wiersz lub całą kolumnę. Biorąc pod uwagę matrycę kolorów wszystkich komórek planszy, znajdź minimalną liczbę operacji malowania, aby pomalować planszę.

Na przykład należy malowanie 3 x 3 płytę w następujący sposób (R - czerwony, B - niebieski, G - zielone)

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

minimalna liczba operacji malowania 4:

• rzędu 0 do malowania z Blue
• farbą rzędu 1 z Red
• Farba wiersz 2 z Zielonego
• kolumnie farbą 0 z Blue

Jak go rozwiązać?

Answer 1

Na początek można wypróbować z wyczerpującym przeszukaniem pod numerem.

Pozwól, aby wykresy stanów były: G=(V,E) gdzie V = {all possible boards} i E = {(u,v) | you can move from board u to v within a single operation}.

• Zauważ, że nie ma potrzeby, aby wygenerować wykres z góry - można wygenerować je na bieżąco, za pomocą successors(board) funkcji, które zwracają wszystkie następców danej planszy.

Potrzebny będzie również h:V->R - ocenia się, że admissible heuristic function płytę .

Teraz możesz uruchomić A* lub bi-directional wyszukiwanie BFS [lub ich kombinację], twoje źródło będzie białą tablicą, a twoim celem będzie żądana tablica. Ponieważ używamy dopuszczalnej funkcji heurystycznej - A * jest zarówno complete (zawsze znajdzie rozwiązanie, jeśli istnieje) i optimal (znajdzie najkrótsze rozwiązanie), znajdzie najlepsze rozwiązanie. [to samo dotyczy dwukierunkowego BFS].

wady:

• Chociaż algorytm jest informowany, będzie miał gwałtowny zachowanie. Ale jeśli jest to pytanie wywiadowcze, uważam, że nieefektywne rozwiązanie jest lepsze niż brak rozwiązania.
• Chociaż kompletny i optymalny - jeśli nie ma rozwiązania - algorytm może utknąć w nieskończonej pętli lub bardzo długiej pętli, dopóki nie zorientuje się, że wyładował wszystkie możliwości.

(1) przykładem dopuszczalnej heurystyki jest h(board) = #(miscolored_squares)/max{m,n}

Answer 2

To wygląda jak zabawa problemu. Pozwól, że rzucę na niego z pseudokodami.

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 

Myślę, że to rozwiąże Twój problem, ale nie próbowałem żadnej optymalizacji ani niczego. To może nie być wystarczająco szybkie, nie wiem. Wątpię, aby problem ten był rozwiązywany w czasie krótszym niż wykładniczy.

Oto jak ten algorytm rozwiązałoby przykład:

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