Максимальный размер квадратной подматрицы со всеми 1s

Question

Учитывая двоичную матрицу, я обнаружил квадратную подматрицу максимального размера со всеми 1 s.

Для примера рассмотрим ниже двоичную матрицу:

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

Максимальная площадь суб-матрица со всеми установленными битами является

1 1 1 
1 1 1 
1 1 1 

Я искал в Интернете для решения, и я нашел отношение к построить вспомогательную матрицу:

If M[i][j] is 1 then 
      S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1 
     Else /*If M[i][j] is 0*/ 
      S[i][j] = 0 

1. Где M[][] является исходной матрицей, а s[][] является вспомогательной матрицей?
2. Что это означает?
3. И как это полезно.

Answer 1

Это классическая проблема динамического программирования. И у не упоминается весь алгоритм, который выглядит следующим образом:

Для построения вспомогательного массива мы должны сделать следующее:

1. сначала скопировать первую строку и первый столбец, как это от M [] [] для S [] []

2. а для остальных записей, как у упомянутых необходимо выполнить следующие действия:

   If M[i][j] is 1 then 
       S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1 
   Else /*If M[i][j] is 0*/ 
       S[i][j] = 0 
   

3. Найти максимальный элемент в S [] [] и использовать его, чтобы построить максимального размер квадратной подматрицу

Что означает это отношение?

Чтобы найти максимальный квадрат, нам нужно найти минимальное расширение 1s в разных направлениях и добавить 1 к нему, чтобы сформировать длину квадрата, заканчивающегося в данном случае.

так для случая s [] [] будет:

0 1 1 0 1 
    1 1 0 1 0 
    0 1 1 1 0 
    1 1 2 2 0 
    1 2 2 3 1 
    0 0 0 0 0 

Если мы просто взять минимум из них, то есть S[i][j-1], S[i-1][j], он заботится о левой и верхней direction.However, мы также должны сделать убедитесь, что в верхнем левом углу перспективного квадрата находятся 1. S [i-1] [j-1] по определению содержит максимальный квадрат в позиции i-1, j-1, верхний левый угол которого устанавливает верхний предел того, как вверх и влево мы можем получить. Поэтому мы должны это учитывать.

Надеюсь, это поможет!

Answer 2

Вы можете создать дополнительную рекурсивную функцию, которая получает в качестве аргумента currect row и col и ищет квадрат любого размера из него.

Из другой функции, после того, как дополнительная функция возвращает значение, вы должны сделать 2 вызова: один из (строка, col + 1), а другой 1 из (строка + 1, col).

Это использование обратного слежения, мы проверяем все варианты.

Answer 3

Вы можете сделать это в линейном времени.

Претензия: Я могу построить структуру данных в линейном времени, что позволяет мне проверять в постоянное время, будет ли произвольный прямоугольник заполнен 1.

Доказательство: Частичные суммы; возьмите S[i][j], чтобы быть общим числом 1 и выше слева от (i, j). Число единиц в прямоугольнике между (a,b) и (c,d), при условии, что (a,b) находится выше и осталось от (c,d), составляет S[c][d] + S[a][b] - S[a][d] - S[b][c].

Теперь это простое сканирование по массиву:

size = 1; 
For i = 0 to m-size { 
    For j = 0 to n-size { 
    If S[i+size][j+size] - S[i][j+size] - S[i+size][j] + S[i][j] == size*size { 
     size++; j--; continue; 
    } 
    } 
} 

В конце size это один больше, чем самая большая 1-полная площадь.