Rectangulaire dans un tableau

Question

Étant donné une matrice N * N ayant 1s un 0 et un entier k, quelle est la meilleure méthode pour trouver une région rectangulaire de telle sorte qu'elle ait k 1 ???

Answer 1

Tenir compte de ce problème plus simple:

Étant donné un vecteur de taille N ne contenant que les valeurs 1 et 0, trouver une suite qui contient exactement les valeurs de k de 1 en elle.

Soit A le vecteur donné et S[i] = A[1] + A[2] + A[3] + ... + A[i], ce qui signifie combien de 1s il y a dans la sous-séquence A[1..i]. Pour chaque i, nous sommes intéressés par l'existence d'un j <= i tel que S[i] - S[j-1] == k.

Nous pouvons trouver dans O(n) avec une table de hachage en utilisant la relation suivante:

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]) 

Maintenant, nous pouvons l'utiliser pour résoudre votre problème donné dans O(N^3): pour chaque séquence de lignes dans votre matrice donnée (il y a O(N^2) séquences de lignes), considérez cette séquence pour représenter un vecteur et appliquer l'algorithme précédent. Le calcul de S est un peu plus difficile dans le cas de la matrice, mais ce n'est pas si difficile à comprendre. Faites-moi savoir si vous avez besoin de plus de détails.

Mise à jour: Voici comment l'algorithme fonctionnerait sur la matrice suivante, en supposant k = 12:

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

Tenir compte de la première ligne seule:

0 1 1 1 1 0 

Considérez-être le vecteur 0 1 1 1 1 0 et appliquez l'algorithme pour le problème le plus simple: nous trouvons qu'il n'y a pas de sous-séquence additionnant jusqu'à 12, donc nous passons à autre chose.

considérerons les deux premiers rangs:

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

Tenir compte qu'ils soient le vecteur 0+0 1+1 1+1 1+1 1+1 0+0 = 0 2 2 2 2 0 et appliquer l'algorithme pour le problème plus simple à ce sujet: encore une fois, pas qui ajoute séquence à 12, afin de progresser.

Tenir compte les trois premières lignes:

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

Tenir compte qu'ils soient le vecteur 0 3 3 3 3 0 et appliquer l'algorithme pour le problème plus simple là-dessus: on trouve la séquence de démarrage en position 2 et se terminant à la position 5 être la solution. De ceci nous pouvons obtenir le rectangle entier avec la comptabilité simple.

Answer 2

Je peux le faire avec O (N^3 * log (N)), mais je suis sûr que la meilleure solution est plus rapide. D'abord vous créez une autre matrice N * N B (la matrice initiale est A). La logique de B est la suivante:

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

Vous pouvez évaluer B à O (N^2) par la programmation dynamique: B [i] [j] = B [i-1] [j] + B [ i] [j-1] - B [i-1] [j-1] + A [i] [j].

Maintenant, il est très facile de résoudre ce problème avec O (N^4) en itérant tout en bas à droite (i = 1..N, j = 1..N, O (N^2)), en bas à gauche (z = 1..j, O (N)), et en haut à droite (t = 1..i, O (N)) et vous obtenez le nombre d'unités dans ce rectangle à l'aide de B:

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

Si vous avez exactement k: k == sum_of_ones, alors vous obtenez le résultat. Pour le rendre N^3 * log (N), vous devriez trouver la recherche binaire droite-supérieure (ne pas simplement répéter toutes les cellules possibles).