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

Question

У меня есть небольшая программа для работы на Java. У меня есть 2D-массив, заполненный 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  

Проблема аналогична this SO question.

Если у вас есть какие-либо идеи, разместите его здесь.

Answer 1

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

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

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

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

Answer 2

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

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

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 этим числа не более размером rhombus.Not уверен, как это работает на огромных массивах. (Я петля эта функция n/2 раза)