Поиск наибольшей квадратной подматрицы единиц в заданной квадратной матрице 0 и 1?

Question

Далее был дан как вопрос интервью:

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

Пример 1:

0 1 
0 0 

Выход: 1

Пример 2:

0 0 0 
0 1 1 
0 1 1 

Выход: 2

Пример 3:

1 1 1 
1 1 1 
1 1 1 

Выход 3

Я надеялся, что для эффективного решения этой проблемы, если вообще возможно.

Answer 1

Использовать Search, а затем Dynamic Programming.

Answer 2

Первая идея реализации: Начать поиск по строке r = 1.

Найдите самую длинную последовательность из них в этой строке и присвойте ей длину.

Попробуйте найти квадратную матрицу из них со стороной = x, начиная с строки r. В случае успеха max = x. Если нет, уменьшите x и повторите этот шаг, если x> 1. Если ничего не найдено, max может быть 0 или 1.

Увеличение r и повторение.

Затем улучшите свой алгоритм (остановитесь, если оставшиеся строки меньше текущего максимума и т. Д.).

Answer 3

Реализация O (n) в C# с использованием динамического программирования. В основном вы строите другую матрицу самого большого размера (включая себя), в то время как вы читаете каждую ячейку матрицы.

public static int LargestSquareMatrixOfOne(int[,] original_mat) 
    { 
     int[,] AccumulatedMatrix = new int[original_mat.GetLength(0), original_mat.GetLength(1)]; 
     AccumulatedMatrix[0, 0] = original_mat[0, 0]; 
     int biggestSize = 1; 
     for (int i = 0; i < original_mat.GetLength(0); i++) 
     { 
      for (int j = 0; j < original_mat.GetLength(1); j++) 
      { 
       if (i > 0 && j > 0) 
       { 
        if (original_mat[i, j] == 1) 
        { 
         AccumulatedMatrix[i, j] = Math.Min(AccumulatedMatrix[i - 1, j - 1], (Math.Min(AccumulatedMatrix[i - 1, j], AccumulatedMatrix[i, j - 1]))) + 1; 
         if (AccumulatedMatrix[i, j] > biggestSize) 
         { 
          biggestSize = AccumulatedMatrix[i, j]; 
         } 
        } 
        else 
        { 
         AccumulatedMatrix[i, j] = 0; 
        } 
       } 
       else if ((i > 0 && j == 0) || (j > 0 && i == 0)) 
       { 
        if (original_mat[i, j] == 1) { AccumulatedMatrix[i, j] = 1; } 
        else { AccumulatedMatrix[i, j] = 0; } 
       } 
      } 
     } 
     return biggestSize; 
    }