Pod-macierz kwadratowa o maksymalnym rozmiarze z wszystkimi 1:

Question

Biorąc pod uwagę macierz binarną, znalazłem kwadratową pod-macierz o maksymalnym rozmiarze z wszystkimi 1 s.

Na przykład, należy rozważyć poniższe binarna matryca:

0 1 1 0 1 
    1 1 0 1 0 
    0 1 1 1 0 
    1 1 1 1 0 
    1 1 1 1 1 
    0 0 0 0 0 

maksymalna kwadratu pod-macierzą wszystkie zestaw bitów

1 1 1 
1 1 1 
1 1 1 

Przeszukiwałam wstęgi rozwiązań i znaleźli stosunku do konstruktu pomocniczego matrycy:

If M[i][j] is 1 then 
      S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1 
     Else /*If M[i][j] is 0*/ 
      S[i][j] = 0 

1. Gdzie M[][] jest oryginalną matrycą, a s[][] jest matrycą pomocniczą?
2. Co oznacza ta relacja?
3. Jak to jest pomocne.

Answer 1

Jest to klasyczny problem z programowaniem dynamicznym. I U nie wspomniano całą algorytm, który jest następujący:

celu skonstruowania pomocniczy układ mamy wykonać następujące czynności:

1. należy skopiować pierwszym rzędzie i w pierwszej kolumnie jest z M [] [] do S [] []

2. a dla pozostałych pozycji jak u wymienić należy:

   If M[i][j] is 1 then 
       S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1 
   Else /*If M[i][j] is 0*/ 
       S[i][j] = 0 
   

3. Znajdź maksymalną wpisu S [] [] i użyć go do budowy maksymalny rozmiar kwadratowego podmatrycę

Co to relacja oznacza?

Aby znaleźć maksymalny kwadrat, musimy znaleźć minimalne rozszerzenie 1s w różnych kierunkach i dodać 1 do niego, aby utworzyć długość kwadratowego zakończenia w tym przypadku.

tak jak w Twoim przypadku s [] [] będzie:

0 1 1 0 1 
    1 1 0 1 0 
    0 1 1 1 0 
    1 1 2 2 0 
    1 2 2 3 1 
    0 0 0 0 0 

Gdybyśmy po prostu wziąć minimum nich tj S[i][j-1], S[i-1][j], to dba o lewym i górnym direction.However, musimy też zrobić jasne, że są 1 w lewym górnym rogu kwadratu perspektywy. S [i-1] [j-1], z definicji, zawiera maksymalny kwadrat na pozycji i-1, j-1, którego lewy górny róg, określa górny limit na to, w jaki sposób możemy uzyskać lewy i prawy. Dlatego też musimy to rozważyć.

Mam nadzieję, że to pomoże!

Answer 2

Można zbudować dodatkową funkcję rekursywną, która dostaje jako argumenty poprawny wiersz i kolumnę, i szuka kwadratu w dowolnym rozmiarze.

Z drugiej funkcji, po czym dodatkowa funkcja zwraca wartość, musisz wykonać 2 połączenia: jeden z (wiersz, col + 1) i drugi 1 z (wiersz + 1, col).

Jest to użycie cofania, sprawdzamy wszystkie opcje.

Answer 3

Możesz to zrobić w czasie liniowym.

Żądanie: Mogę zbudować strukturę danych w czasie liniowym, która pozwala mi sprawdzić w stałym czasie, czy arbitralny prostokąt jest pełen 1-ek.

Dowód: częściowe kwoty; weź S[i][j], aby uzyskać całkowitą liczbę 1 powyżej i na lewo od (i, j). Liczba elementów w prostokącie między (a,b) i (c,d), pod warunkiem, że (a,b) jest powyżej i po lewej stronie (c,d), to S[c][d] + S[a][b] - S[a][d] - S[b][c].

Teraz to proste skanowanie na tablicy:

size = 1; 
For i = 0 to m-size { 
    For j = 0 to n-size { 
    If S[i+size][j+size] - S[i][j+size] - S[i+size][j] + S[i][j] == size*size { 
     size++; j--; continue; 
    } 
    } 
} 

Na koniec size jest większa niż największa 1-pełnego kwadratu.