Bonjour,
On m'a conseillé un site pour apprendre l'algorithmique, alors je me suis dit "why not?", et de plus cela me permettrait de voir les résultats de l'année à la fac ^^

Mais je bloque sur un exercice. Voici les consignes et un exemple :
LIMITES DE TEMPS ET DE MEMOIRE (Langage : C)

Temps : 0.5s sur une machine à 1Ghz.
Mémoire : 64000 Ko.

CONTRAINTES

1 <= nbLignes, nbColonnes <= 350

ENTRÉE

Sur la première ligne : deux entiers nbLignes et nbColonnes
Les nbLignes lignes suivantes comportent chacun nbColonnes entiers compris entre 0 et 1 séparés par des espaces. 0 signifie qu'il n'y a pas de moustiques et 1 qu'il y a des moustiques
SORTIE

Un unique entier : la taille maximale du côté d'un carré ne comportant que des 0 et dont les bords sont parallèles aux axes.

EXEMPLE 1

entrée :
6 7
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
sortie :
4
Mon code est bon, le problème est l'optimisation. Sur les 22 tests, 3 échouent car trop longs. Et je ne vois pas du tout comment optimiser d'avantage..
Voici le code :
Code c : 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
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;
}
Merci de votre aide =)

PS : Si problème il y a, car l'exo est bien avancé etc, je supprimerais le code, bien entendu. Je l'enverrais alors par MP, ce qui sera moins pratique quand même ^^'