W kwadratowej macierzy, gdzie każda komórka jest czarna lub biała. Zaprojektuj algorytm, aby znaleźć maksymalny pod-kwadrat, tak aby wszystkie 4 obramowania były czarne.

Question

Otrzymano kwadratową macierz, w której każda komórka jest czarna lub biała. Zaprojektuj algorytm, aby znaleźć maksymalny pod-kwadrat, tak aby wszystkie 4 granice były czarne.

mam O (N^2) Algorytm:

skanowania każda kolumna od lewej do prawej strony, dla każdej komórki w każdej kolumnie, skanowanie każdy rząd na znalezienie max sub-kwadrat z tyłu granicą.

Czy istnieją lepsze rozwiązania?

dzięki

Answer 1

O (n^2) jest możliwe. Sądzę, że jest optymalna, ponieważ masz n^2 komórek.

Należy zauważyć, że lewy górny róg i prawy dolny róg dowolnego kwadratu leżą wzdłuż tej samej przekątnej.

Teraz, jeśli moglibyśmy przetworzyć każdą przekątną w czasie O (n), mielibyśmy algorytm czasu O (n^2).

Powiedzmy, że mamy kandydata na lewy górny róg. Możemy obliczyć liczbę ciągłych czarnych komórek poniżej i na prawo od niego i wziąć minimum dwóch i nazwać je T.

Dla kandydata z prawą dolną, możemy obliczyć liczbę ciągłych czarnych komórek po lewej stronie i na górze, i weź co najmniej dwa, nazwij go B.

Gdy mamy dwie liczby T i B, możemy stwierdzić, czy dany lewy i prawy górny kandydat właściwie daje nam kwadrat ze wszystkimi czarnymi granicami.

Teraz te dwie liczby można obliczyć dla każdej komórki, w czasie O (n^2), wykonując cztery przebiegi całej macierzy (Jak?).

Załóżmy, że to się stało.

Teraz rozważ przekątną. Naszym celem jest znalezienie lewej górnej, dolnej i prawej pary wzdłuż tej przekątnej w czasie O (n).

Załóżmy, że mamy T obliczone w tablicy T [1 ... m], gdzie m jest długością przekątnej. Podobnie mamy tablicę B [1 ... m]. T [1] odpowiada lewemu górnemu krańcowi przekątnej i T [m] prawemu dolnemu. Podobnie z B.

Teraz przetwarzamy przekątną w następujący sposób, dla każdego kandydata z górnej lewej strony, staramy się znaleźć kandydata z prawym dolnym kątem, który da największy kwadrat. Zauważ, że j> = i. Zauważ również, że jeśli (i, j) jest kandydatem, to (i ', j) nie jest, gdzie i>>.

Należy zauważyć, że i i j tworzą kwadrat, jeśli T[i] >= j-i+1 i B[j] >= j-i+1.

tj. T[i] +i - 1 >= j i B[j] -j - 1 >= -i.

Tak więc tworzymy nowe tablice takie, że TL[k] = T[k] + k -1 i BR[k] = B[k] -k - 1.

Więc biorąc pod uwagę TL dwie nowe tablice i BR, oraz ja, musimy odpowiedzieć na następujące pytania:

Co jest największym j takie, że TL [i]> = j i BR [j ]> = -i?

Załóżmy teraz, że udało nam się przetworzyć BR dla maksymalnych zapytań dotyczących zakresu (można to zrobić w czasie O (m)).

Teraz podając TL [i], w zakresie [i, TL [i]] znajdujemy maksymalną wartość BR, np. BR [j1].

Teraz, jeśli BR [j1]> = -i, znajdujemy maksimum BR w zakresie [j1, TL [i]] i kontynuujemy w ten sposób.

Po znalezieniu kandydata (TL [i], BR [j]), możemy zignorować tablicę BR [1 ... j] dla przyszłego i.

To pozwala nam przetwarzać każdą przekątną w czasie O (n), dając całkowity algorytm O (n^2).

Zostawiłem wiele szczegółów i otrzymałem szkic, który był już zbyt długi. Możesz to edytować, dodając wyjaśnienia.

Uff.

Answer 2

C++ Kod:

#include<iostream> 
using namespace std; 

int min(int a,int b,int c) 
{ 
    int min = a; 
    if(min > b) 
     min = b; 
    if(min > c) 
     min = c; 
    return min; 
} 

int main() 
{ 
    const int size = 5; 
    char a[size][size] = { {'b','b','b','b','w'},{'b','b','b','b','b'},{'b','b','b','b','b'},{'b','b','w','b','b'},{'b','w','w','b','b'} }; 
    int arr[size+1][size+1]; 
    // First row and First column of arr is zero. 
    for(int i=0;i<size+1;i++) 
    { 
     arr[0][i] = 0; 
     arr[i][0] = 0; 
    } 
    int answer = 0; 
    for(int i=0;i<size;i++) 
    { 
     for(int j=0;j<size;j++) 
     { 
      if(a[i][j] == 'w') 
       arr[i+1][j+1] = 0; 
      if(a[i][j] == 'b') 
      { 
       int minimum = min(arr[i][i],arr[i+1][j],arr[i][j+1]); 
       arr[i+1][j+1] = minimum + 1; 
       if(arr[i+1][j+1] > answer) 
        answer = arr[i+1][j+1]; 
      } 
     } 
    } 
    for(int i=0;i<size+1;i++) 
    { 
     for(int j=0;j<size+1;j++) 
     { 
      cout<<arr[i][j]<<"\t"; 
     } 
     cout<<endl; 
    } 
    cout<<answer<<endl; 
    return 0; 
} 

Answer 3

/* In a square matrix, where each cell is black or white. 
* Design an algorithm to find the max sub-square such that all 4 borders are black. The right Java implementation based on a previous post. 
*/ 
public int maxSubsquare(boolean[][] M){ 
    int n = M.length; 
    maxsize=0; 
    checkDiag(M, 0, 0, n); 
    for (int i=1; i<n; i++){ 
     checkDiag(M, i, 0, n); 
     checkDiag(M, 0, i, n); 
    } 
    return maxsize; 
} 
int maxsize; 
void checkDiag(boolean[][] M, int i, int j, int n){ 
    if (i>=n-maxsize || j>=n-maxsize) return; 
    int step = 0; 
    while (step<(n-Math.max(i, j))&& M[i][j+step]&&M[i+step][j]){ 
     int s = step; 
     while (s>0){ 
      if (M[i+s][j+step]&&M[i+step][j+s]) s--; 
      else break; 
     } 
     if (s==0) 
      maxsize = Math.max(maxsize, step+1); 
     step++; 
    } 
    if (step==0) checkDiag(M, i+step+1, j+step+1, n); 
    else checkDiag(M, i+step, j+step, n); 
} 

Answer 4

nie wiem dlaczego można uzyskać algorytm O (n^2). Matematycznie jest to niemożliwe. Załóżmy, że masz macierz NxN. Musisz sprawdzić: 1. 1 macierz wielkości: NxN, 2. 2 * 2 macierzy wielkości: (N-1) x (N-1), 3. 3 * 3 macierze wielkości: (N- 2) x (N-2), ....

W sumie musisz sprawdzić: 1+ 2^2 + 3^2 + ... + N^2 = N (N + 1) (2N + 1)/6. Więc każdy algorytm nie może zrobić lepiej niż O (N^3)