En una matriz cuadrada, donde cada celda es negra o blanca. Diseñe un algoritmo para encontrar el máximo cuadrado de manera que los 4 bordes sean negros

Question

Dada una matriz cuadrada, donde cada celda es negra o blanca. Diseña un algoritmo para encontrar la subcuadrícula máxima de modo que los 4 bordes sean negros.

tengo O (n^2) algoritmo:

Scan cada columna de izquierda a derecha, para cada célula en cada columna, escanear cada fila para encontrar el sub-max cuadrado con bordes traseros.

¿Hay mejores soluciones?

gracias

Answer 1

O (n^2) es posible. Supongo que es óptimo, ya que tienes n^2 células.

Observe que la esquina superior izquierda y la esquina inferior derecha de cualquier cuadrado se encuentran en la misma diagonal.

Ahora si pudiéramos procesar cada diagonal en O (n) tiempo, tendríamos un algoritmo de tiempo O (n^2).

Supongamos que tenemos un candidato para la esquina superior izquierda. Podemos calcular el número de celdas negras continuas debajo de él, y a la derecha del mismo, tomar el mínimo de los dos y llamarlo T.

Para un candidato de la esquina inferior derecha, podemos calcular el número de celdas negras continuas a la izquierda, y arriba y tome el mínimo de los dos, llámelo B.

Una vez que tenemos los dos números T y B, podemos decir si el candidato arriba a la izquierda, abajo a la derecha de hecho, danos un cuadrado con todos los bordes negros.

Ahora esos dos números se pueden calcular para cada celda, en O (n^2) tiempo haciendo cuatro pasadas a través de la matriz completa (¿Cómo?).

Así que supongamos que ya está hecho.

Considere ahora una diagonal. Nuestro objetivo es encontrar un par superior izquierdo, inferior derecho a lo largo de esta diagonal en el tiempo O (n).

Supongamos que tenemos las T calculadas en una matriz T [1 ... m] donde m es la longitud de la diagonal. Del mismo modo, tenemos una matriz B [1 ... m]. T [1] corresponde al extremo superior izquierdo de la diagonal y T [m] a la inferior derecha. De manera similar con B.

Ahora procesamos la diagonal de la siguiente manera, para cada candidato de la parte superior izquierda i, tratamos de encontrar un candidato de abajo a la derecha j que dará el cuadrado más grande. Observe que j> = i. También note que si (i, j) es un candidato, entonces (i ', j) no es, donde i'> i.

Tenga en cuenta que i y j forman un cuadrado si T[i] >= j-i+1 y B[j] >= j-i+1.

es decir, T[i] +i - 1 >= j y B[j] -j - 1 >= -i.

Así que formamos nuevas matrices tales como TL[k] = T[k] + k -1 y BR[k] = B[k] -k - 1.

Por lo tanto, dada la TL dos nuevas matrices y BR, y un i, tenemos que responder a las siguientes preguntas:

¿Cuál es el j grande tal que TL [i]> = j y BR [j ]> = -i?

Supongamos ahora que pudimos procesar BR para consultas de rango máximo (se puede hacer en O (m) tiempo).

Ahora dado TL [i], en el rango [i, TL [i]] encontramos el valor máximo de BR, digamos BR [j1].

Ahora, si BR [j1]> = -i, encontramos el máximo de BR en el rango [j1, TL [i]] y continuamos de esta manera.

Una vez que encontramos el candidato (TL [i], BR [j]), podemos ignorar la matriz BR [1 ... j] para el futuro i.

Esto nos permite procesar cada diagonal en O (n) tiempo, dando un algoritmo total O (n^2).

He omitido muchos detalles y he dado un boceto, ya que ya era demasiado largo. Siéntase libre de editar esto con aclaraciones.

Phew.

Answer 2

C++ Código:

#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

No sé qué puede obtener un O (n^2) algoritmo. Matemáticamente, es imposible. Digamos que tiene una matriz NxN. Debe verificar: 1. 1 matriz de tamaño: NxN, 2. 2 * 2 matrices de tamaño: (N-1) x (N-1), 3. 3 * 3 matrices de tamaño: (N- 2) x (N-2), ....

En total, debe verificar: 1+ 2^2 + 3^2 + ... + N^2 = N (N + 1) (2N + 1)/6. Así que cualquier algoritmo no puede ser mejor que O (N^3)