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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
| #include <stdio.h>
#include <stdlib.h>
int etendreCarre(int **tab, int debLig, int debCol, int taille, int nbLig, int nbCol) { //Ajoute une colonne et une ligne, et vérifie si le nouveau carré formé est toujours vide
int bon=1, i=debLig+taille-1, j=debCol, res;
if (debLig+taille > nbLig || debCol+taille > nbCol) return 0;
while (bon && j < debCol+taille) {
if (tab[i][j]) bon=0;
else j++;
}
if (bon) j--;
while (bon && i >= debLig) {
if (tab[i][j]) bon=0;
else i--;
}
if (bon) {
if ((res=etendreCarre(tab,debLig,debCol,taille+1,nbLig,nbCol)))
return res;
else
return taille;
}
else
return 0;
}
int tailleCarre(int **tab, int debLig, int debCol, int taille, int nbLig, int nbCol) { //Vérifie si le carré de coté taille est vide
int bon =1, i=debLig, j=debCol, res;
while (bon && i < nbLig && i < debLig+taille) {
j=debCol;
while (bon && j < nbCol && j < debCol+taille) {
if (tab[i][j])
bon=0;
else
j++;
}
i++;
}
if (i==debLig+taille && j==debCol+taille) {
if ((res=etendreCarre(tab,debLig,debCol,taille+1,nbLig,nbCol)))
return res;
else
return taille;
}
else
return 0;
}
int main (int argc, char **argv) {
int nbLig, nbCol, i, j, **tab, taille=0, max=0;
scanf("%d %d",&nbLig,&nbCol);
if (nbLig > 350 || nbLig < 1 || nbCol > 350 || nbCol < 1)
exit(0);
tab=malloc(sizeof(int)*nbLig);
for (i=0; i < nbLig; i++){
tab[i]=malloc(sizeof(int)*nbCol);
for (j=0; j < nbCol; j++) {
scanf("%d",&tab[i][j]);
}
}
for (i=0; i < nbLig; i++){
for (j=0; j < nbCol; j++) {
if (!tab[i][j] && i+max < nbLig && j+max < nbCol) {
taille=tailleCarre(tab,i,j,max+1,nbLig,nbCol);
if (taille > max)
max=taille;
}
else if (j+max >= nbCol) break;
else if (i+max >= nbLig) continue;
}
}
printf("%d",max);
for (i=0; i < nbLig; i++)
free(tab[i]);
free(tab);
return 0;
} |
