Programmation dynamique: Trouver le plus gros diamant (losange)

Question

J'ai un petit programme à faire en Java. J'ai un tableau 2D rempli de 0 et 1, et je dois trouver le plus grand losange (comme en carré tourné de 45 degrés) et leurs nombres.

Exemple:

 
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 

Résultat:

 
     1  

    1 1 1 

    1 1 1 1 1 

    1 1 1 

     1  

Le problème est similaire à this SO question.

Si vous avez une idée, inscrivez-la ici.

Answer 1

Ceci est trop long pour un commentaire. Je posterai ma solution plus tard si vous ne pouvez pas la résoudre mais voici comment je l'ai fait (en moins de 15 lignes de code): J'ai d'abord créé un second tableau (un peu plus gros [n + 2] [ n + 2]) et a fait n/2 passe:

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 

Lorsqu'un non nul x signifie « Je suis au centre d'une taille x de losange » (j'exprime la taille en relation avec la longueur des diagonales [qui sont toutes deux égales dans votre cas] du losange). Vous pouvez trouver si vous avez le centre d'un losange de taille (k + 1) en vérifiant si {haut, droite, bas, gauche} sont tous les centres de losange de taille k. L'avantage de créer d'abord un tableau plus grand est qu'il simplifie vraiment votre logique mais je pourrais le faire en place, avec une logique plus alambiquée, en modifiant le tableau original ou en utilisant un second tableau de la même taille que le entrée (encore une fois, il est plus facile de mettre simplement une "clôture" sûre de zéros autour de votre entrée). Si vous n'entourez pas votre tableau avec une clôture, vous avez beaucoup de vérifications if/else supplémentaires: ce serait sujette aux erreurs, conduirait à un code plus grand et conduirait à un code plus laid.

Answer 2

tutoriel court:

Comment voulez-vous résoudre le problème si elle était un 1x1 -field?
Comment pourriez-vous formuler le problème récursivement?
Comment pourriez-vous vous souvenir des résultats intermédiaires et les utiliser?
Faites-le.

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]; 
        } 
       } 
      } 
     } 
    } 
} 

l'a fait, cela fonctionne, cela est ma fonction, où MAXR est la taille maximale du losange, et NRR est le nombre maximum de taille rhombus.Not sûr de savoir comment il fonctionne sur des réseaux énormes. (Boucle i Cette fonction n/2 fois)