Непрерывный Все один блок в матрице

Предположим, вам задано растровое изображение mXn, представленное массивом M[1..m,1..n], все элементы которого равны 0 или 1. Блок, состоящий из единиц, представляет собой подмассив формы M[i..i0, j .. j0], в котором каждый бит равен 1. Описать и проанализировать эффективный алгоритм нахождения в M блока, состоящего из всех единиц, с максимальной площадью

Я пытаюсь сделать решение для динамического программирования. Но мой рекурсивный алгоритм работает за время O(n^n), и даже после мемоизации я не могу думать о том, чтобы снизить его ниже O(n^4). Может ли кто-нибудь помочь мне найти более эффективное решение?


memoization dynamic-programming
person Xero    schedule 26.09.2010    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Это только идея, и я не уверен, что она работает.

Определить A(i,j)(di,dj) как один блок от (i,j) до (i+di,j+dj), что означает M[x,y]=1 для i‹=x ‹=i+di и j‹=y‹=j+dj.

Определить A(i,j)(di,dj) как max-block, если не содержит A(i,j)(di+1,dj) и A(i,j)( ди, дж+1).

Для каждого (i,j) мы можем построить список, назовем его L(i,j), из максимальных блоков. Максимальная длина списка составляет min(m-i+1, n-j+1) ‹= min(m,n).

L(i,j) зависит только от M[i,j], L(i+1,j) и L(i,j+1). Я думаю, что построить L(i,j) из L(i+1,j) и L(i,j+1) можно за линейное время, это напоминает мне слияние отсортированных списков. Используя L(i,j), найдите max(di * dj) для A(i,j)(di,dj) в L(i,j). Максимальное из этих значений указывает максимальный блок "все-один".

Этот подход имеет сложность n*m*min(m,n) ~= n^3 и требует минимального (m,n)^2 пространства для хранения последних двух строк, которые необходимы.

person Ante    schedule 10.11.2010