Динамическое программирование: найти самый большой бриллиант (ромб)

Question

У меня есть небольшая программа на Java. У меня есть двумерный массив, заполненный 0 и 1, и я должен найти самый большой ромб (как в квадрате, повернутом на 45 градусов) и их числа.

Пример:

0 1 0 0 0 1

1 0 1 1 1 0

1 0 1 1 1 1

0 1 1 1 1 1

0 0 1 1 1 1

1 1 1 1 1 1

Результат:

      1    

    1 1 1  

  1 1 1 1 1

    1 1 1  

      1    

Проблема похожа на этот вопрос SO .

Если у вас есть идея, опубликуйте ее здесь.

Answer 1

Это слишком долго для комментария. Я опубликую свое решение позже, если вы не можете решить его, но вот как я это сделал (менее чем в 15 строках кода): я сначала создал второй массив (немного больше, больше [n + 2] [ n + 2]) и сделали n / 2 пас:

0 0 0 0 0 0 0 0 
0 0 1 0 0 0 1 0 
0 1 0 1 1 1 0 0 
0 1 0 1 2 2 1 0 
0 0 1 2 2 2 1 0 
0 0 0 1 2 2 1 0 
0 1 1 1 1 1 1 0 
0 0 0 0 0 0 0 0 

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

Где ненулевое число x означает «Я - центр ромба размера x» (я выражаю размер в зависимости от длины диагоналей [которые в вашем случае равны) ромб). Вы можете определить, есть ли у вас центр ромба размера (k + 1), проверив, все ли {сверху, справа, вниз, влево} центры ромба размера k.

Преимущество первого создания массива большего размера состоит в том, что он действительно упрощает вашу логику, но я мог бы сделать это на месте, с более запутанной логикой, изменив исходный массив или используя второй массив того же размера, что и входные данные (еще раз, гораздо проще просто поставить безопасный «забор» из всех нулей вокруг вашего ввода).

Если вы не «окружаете» свой массив забором, у вас есть много дополнительных проверок if / else: это может привести к ошибкам, привести к большему коду и к более уродливому коду.

Answer 2

Краткое руководство:

Как бы вы решили проблему, если бы это было поле 1x1?
Как вы могли бы сформулировать проблему рекурсивно?
Как вы могли запомнить промежуточные результаты и использовать их?
Сделай это.

Answer 3

void rhombus()
{
    maxr=0;
    for (int i=n-1;i>=0;i--)
    {
        for (int j=n-1;j>=0;j--)
        {
            if (b[i][j]>0)
            {
                if ((i==n-1) || (j==n-1) || (i==0) || (j==0)) b[i][j]=1;
                else {
                    b[i][j]=min4(b[i][j+1],b[i][j-1],b[i+1][j],b[i-1][j])+1;
                    if (b[i][j]==maxr) nrr++;
                    else if (b[i][j]>maxr) {
                        nrr=1;
                        maxr=b[i][j];
                    }
                }
            }
        }
    }
}

Сделано, все работает, это моя функция, где maxr - это максимальный размер ромба, а nrr - номер ромба с максимальным размером. Не знаю, как он работает на огромных массивах. 2 раза)