Discussion :

[patoskull]

Bonjour,
Ça fait pas mal de temps que j'essaye de résoudre ce petit problème:
On dispose d'un rectangle rempli de 0 et 1 et on doit trouver le plus grand carré inclus dans ce rectangle qui ce compose de 0.

exemple:

0 0 0 1 1 1 1
0 0 0 1 1 1 1
0 0 0 1 1 1 1
1 1 1 1 1 0 0
1 1 1 1 1 0 0

reponse:3

voici mon code

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <stdio.h>
#include <stdlib.h>
 
 
int main()
{
    int x,y,i,j,l,max=1,boo=1,h;
    scanf("%d %d",&x,&y);
    int map[x][y];
    for(i=0;i<x;i++)
    {
        for(j=0;j<y;j++)
        {
            scanf("%d",&map[i][j]);
        }
    }
 
      for(i=0;i<x;i++)
    {
        for(j=0;j<y;j++)
        {
            boo=1;
            if(map[i][j]==0)
            {
                for(h=0;h<max;h++)
                {
                    if(i+max>=x || j+max>=y) break;
 
                    for(l=0;l<max;l++)
                    {
                        if((map[l+i+1][h+j+1]!=0 || map[l+i][h+j+1]!=0)  || (map[l+i][h+j+1]!=map[h+j+1][l+i]) || (map[l+i+1][h+j+1]!=map[h+j+1][l+i+1]))
                        {
                        boo=0;
                        }
 
 
                    }
                    if(boo==1)  max++;
 
 
 
 
                }
 
 
            }
 
 
 
        }
    }
    printf("%d",max);
 
    return 0;
}

explication: pour
0 0 0 1 1 1 1
0 0 0 1 1 1 1
0 0 0 1 1 1 1
1 1 1 1 1 0 0
1 1 1 1 1 0 0

dès qu'il trouve un zéro le plus grand triangle rectangle isocèle et son symétrique remplie de 0 ici

 0 0 0  
   0 0                                
     0 

et son symétrique c'est

 0
 0 0
 0 0 0

Je ne sais pas pourquoi mon code ne retourne pas toujours le bon résultat par exemple pour:
1 0 0 1 0 0 1
0 0 0 0 0 0 0
1 0 0 0 0 0 0
0 0 0 0 0 0 0
0 1 0 0 0 0 1
1 0 0 0 1 0 1
il retourne 5 au lieu de 4, qu'en pensez vous?

[LittleWhite]

Bonjour,

Je pense que votre erreur est sur l'algorithme, simplement. Il manque une contrainte qui dit que le triangle doit avoir une taille des deux cotés identiques.

Car là, dans le cas où cela ne fonctionne pas, votre algorithme trouve un rectangle de 5x4, en utilisant un triangle 5x4.
(Je parle des cotés autour de l'angle droit.)