Contigus Bloc tout-en-un dans une matrice

Question

Supposons que vous receviez un bitmap mXn, représenté par un tableau M [1..m, 1 .. n] dont les entrées sont tous 0 ou 1. Un bloc entier est une sous-matrice de la forme M [i .. i0, j .. j0] dans laquelle chaque bit est égal à 1. Décrire et analyser un algorithme efficace pour trouver un bloc tout-en M avec une surface maximale

Je suis essayer de faire une solution de programmation dynamique. Mais mon algorithme récursif s'exécute en temps O (n^n), et même après la mémorisation, je ne peux pas penser à l'abaisser en dessous de O (n^4). Quelqu'un peut-il m'aider à trouver une solution plus efficace?

Answer 1

C'est seulement une idée, et je ne suis pas sûr si elle fonctionne bien. Définir A (i, j) (di, dj) comme étant un bloc de (i, j) à (i + di, j + dj), ce qui signifie M [x, y] = 1 pour i = x < < = i + di et j = y < < = j + dj.

définir une (i, j) (di, dj) comme max-bloc s'il ne tient pas A (i, j) (di + 1, dj) et A (i, j) (di , dj + 1).

Pour chaque (i, j) on peut contruct liste, appeler L (i, j), de max-blocs. La longueur maximale de la liste est min (m-i + 1, n-j + 1) < = min (m, n).

L (i, j) ne dépend que de M [i, j], L (i + 1, j) et L (i, j + 1). Je pense que construire L (i, j) à partir de L (i + 1, j) et L (i, j + 1) peut être fait en temps linéaire, cela me rappelle la fusion de listes triées. Avec L (i, j), pour max (di * dj) A (i, j) (di, dj) à L (i, j). La valeur maximale de ces valeurs spécifie un bloc tout-un maximal. Cette approche a une complexité n * m * min (m, n) ~ = n^3 et nécessite un espace min (m, n)^2 pour stocker les 2 dernières lignes qui sont nécessaires.