Найти наибольшую квадратную подматрицу единиц в данной квадратной матрице из 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

Использование Поиск , а затем Динамическое программирование .

Answer 2

Вот реализация 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;
    }

Answer 3

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

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

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

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

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