Región rectangular en una matriz

Question

Dada una matriz N * N con 1's un 0 en ellas y dado un número entero k, ¿cuál es el mejor método para encontrar una región rectangular tal que tenga k 1 en ella ???

Answer 1

consideran este problema más sencillo:

dado un vector de tamaño N que contiene sólo los valores 1 y 0, encontrar una subsecuencia que contiene exactamente k valores de 1 en ella.

Let A el vector dado y S[i] = A[1] + A[2] + A[3] + ... + A[i], lo que significa el número de 1s existen en la subsecuencia A[1..i].

Por cada i, estamos interesados ​​en la existencia de un j <= i tal que S[i] - S[j-1] == k.

Podemos encontrar esto en O(n) con una tabla hash utilizando la siguiente relación:

S[i] - S[j-1] == k => S[j-1] = S[i] - k

let H = an empty hash table 
for i = 1 to N do 
    if H.Contains (S[i] - k) then your sequence ends at i 
    else 
    H.Add(S[i]) 

Ahora podemos usar esto para resolver su problema dado en O(N^3): para cada secuencia de filas en su matriz dada (hay O(N^2) secuencias de filas), considere esa secuencia para representar un vector y aplicarle el algoritmo anterior. El cálculo de S es un poco más difícil en el caso de la matriz, pero no es tan difícil de entender. Déjeme saber si usted necesita más detalles.

Actualización: He aquí cómo el algoritmo trabajaría en la siguiente matriz, suponiendo k = 12:

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

Considérese la primera fila solo:

0 1 1 1 1 0 

Se deben considerar un vector 0 1 1 1 1 0 y aplique el algoritmo para el problema más simple: encontramos que no hay subsecuencias sumando hasta 12, así que seguimos adelante.

Consideremos las dos primeras filas:

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

consideran que son el vector 0+0 1+1 1+1 1+1 1+1 0+0 = 0 2 2 2 2 0 y aplicar el algoritmo para el problema más simple en él: de nuevo, sin subsecuencia que se suma a 12, por lo que seguir adelante.

en cuenta las tres primeras filas:

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

consideran que son el vector 0 3 3 3 3 0 y aplicar el algoritmo para el problema más simple en él: nos encontramos con la secuencia de arranque en la posición 2 y termina en la posición 5 para ser la solución. De esto podemos obtener todo el rectángulo con contabilidad simple.

Answer 2

Puedo hacerlo con O (N^3 * log (N)), pero seguro que la mejor solución es más rápida. Primero crea otra matriz N * N B (la matriz inicial es A). La lógica de B es la siguiente:

B[i][j] - is the number of ones on rectangle in A with corners (0,0) and (i,j). 

puede evaluar B para O (N^2) por programación dinámica: B [i] [j] = B [i-1] [j] + B [ i] [j-1] - B [i-1] [j-1] + A [i] [j].

Ahora es muy fácil resolver este problema con O (N^4) iterando sobre toda la parte inferior derecha (i = 1..N, j = 1..N, O (N^2)), left-bottom (z = 1..j, O (N)), y right-upper (t = 1..i, O (N)) y obtienes el número de unidades en este rectángulo con la ayuda de B:

sum_of_ones = B[i][j] - B[i][z-1] - B[t-1][j] + B[t-1][z-1]. 

Si obtuvo exactamente k: k == sum_of_ones, entonces sale el resultado.

Para convertirlo en N^3 * log (N), debe encontrar la posición superior derecha mediante la búsqueda binaria (por lo tanto, no solo itere todas las celdas posibles).