Найти самую большую квадратную подматрицу

Question

Я пытаюсь найти самую большую квадратную подматрицу с одинаковыми цифрами из матрицы, которая может содержать разные числа

Я нашел несколько ответов, которые, кажется, одинаковы для этой проблемы, но не былилюбой с квадратной подматрицей

    int[,] dp = new int[a.GetLength(0), a.GetLength(1)];
    for (int i = 0; i < a.GetLength(0); i++)
    {
        for (int j = 0; j < a.GetLength(1); j++)
        {
            if (i == 0 || j == 0)
                dp[i, j] = 1;
            else
            {
                if (a[i, j] == a[i - 1, j] &&
                    a[i, j] == a[i, j - 1] &&
                    a[i, j] == a[i - 1, j - 1])
                {
                    dp[i, j] = (dp[i - 1, j] > dp[i, j - 1] &&
                                dp[i - 1, j] > dp[i - 1, j - 1] + 1) ?
                                                        dp[i - 1, j] :
                                (dp[i, j - 1] > dp[i - 1, j] &&
                                 dp[i, j - 1] > dp[i - 1, j - 1] + 1) ?
                                                         dp[i, j - 1] :
                                                  dp[i - 1, j - 1] + 1;
                }
                else dp[i, j] = 1;
            }
        }
    }

               {{7, 4, 7, 7, 7, 7},
                {7, 4, 7, 7, 7, 7},
                {7, 7, 1, 7, 7, 7},
                {7, 7, 3, 7, 9, 7},
                {1, 1, 7, 7, 1, 7},
                {7, 7, 7, 5, 7, 7}}; I expect to get the top right 3x3 submatrix containing 7's

Answer 1

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

    dp[i, j] = Math.Min(Math.Min(dp[i - 1, j], dp[i, j - 1]), dp[i - 1, j - 1]) + 1;

Таким образом, у вас будет следующее решение:

1,1,1,1,1,1
1,1,1,2,2,2
1,1,1,1,2,3
1,2,1,1,1,1
1,1,1,1,1,1
1,1,1,1,1,1

Каждое число представляет, если есть подматрица с предыдущими числами, смотрящая сверху и слева.Таким образом, самая большая подматрица - та, которая имеет 3, начиная с позиции (0,4) и заканчивая (2,6).