Discussion :

[metralla]

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 ^^'

[Trademark]

Salut,

C'est un problème d'algo pas de C alors la prochaine fois poste dans le bon forum ;-) Un algo en temps linéaire est possible :

Code :

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

1
2
3
4
Pour chaque case C contenant 0 et non marquée :
  Trouver le plus grand carré faisable à partir de C (en allant vers la droite et vers le bas)
  Marquer toutes les cases qu'on a visité
  Sauvegarder la taille si le carré est plus grand

Je n'ai pas analysé ton code mais tu avais peut-être pas pensé à marquer les cases que tu as déjà visité ?

EDIT : L'algo est faux Voir message de dinobogan après.

[dinobogan]

Un algo en temps linéaire est possible :

Code :

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

1
2
3
4
Pour chaque case C contenant 0 et non marquée :
  Trouver le plus grand carré faisable à partir de C (en allant vers la droite et vers le bas)
  Marquer toutes les cases qu'on a visité
  Sauvegarder la taille si le carré est plus grand

Je n'ai pas analysé ton code mais tu avais peut-être pas pensé à marquer les cases que tu as déjà visité ?

Malheureusement non. L'exemple donné dans le premier post t'empêcherait de trouver le plus grand carré car le zéro en 2eme ligne 3eme colonne serait marqué et est pourtant le coin du carré le plus grand.

Dans ce genre de problème, il faut tenter de précalculer les informations qui seront souvent utilisées dans l'algorithme de résolution.
Ta matrice va contenir non seulement des uns ou des zéros, mais aussi pour chaque zéro l'étendu en horizontal et en vertical pour une ligne de zéro. Plus clairement, une case (x;y) contenant un zéro va contenir 2 autres entiers : l'abscisse minimum x1 telle que la ligne [(x1;y);(x;y)] contient uniquement des zéros et l'ordonnée minimum y1 telle que la colonne [(x;y1);(x;y)] contient uniquement des zéros.
Ceci fait, deux boucles for imbriquées vont parcourir ligne par ligne à la recherche des zéros. Pour chaque zéro rencontré représentant le coin haut gauche (x;y) d'un nouveau carré, tu vas faire une boucle for pour agrandir le carré par son coin bas droit (x+n ; y+n). Chaque case (x+n ; y+n) contient déjà des informations sur la ligne et la colonne de zéro. Considérons les informations précalculées de (x+n;y+n) :
- si x1 <= x et y1 <= y, alors il existe un carré dont les coins sont (x;y) et (x+n;y+n), tu continus à agrandir ton carré,
- sinon tu ne peux pas agrandir ton carré et tu stockes sa taille si elle est plus grande que la taille précédente.

J'espère avoir été clair

Le précalcul pourrait éventuellement être fait durant l'algo de recherche, à voir si c'est plus rapide : les x1 et y1 de ta matrice serait initialisés à -1. Dans ta recherche, un simple "if" permettrait de savoir si le calcul a déjà été fait. Si ce n'est pas le cas, alors faire le calcul.

[metralla]

Oups désolé, je suis directement allé à la section C, sans penser qu'il y a un forum algo, mea culpa.
Si jamais le forum peut être déplacé à la bonne section ^^

Merci de vos réponses.
@dinobogan si j'ai bien compris, j'aurais donc une matrice contenant des structures. Celles-ci auraient la valeur de la case, le nombre de 0 consécutifs en horizontal, et en vertical, c'est bien ça?
Et pour remplir ces informations je devrais faire en plus deux boucles for imbriquées, qui appelleront deux fonctions pour les remplir.
Mais ça ne risque pas d'être encore plus long? Surtout pour les grandes matrices.

[dinobogan]

Mais ça ne risque pas d'être encore plus long? Surtout pour les grandes matrices.

Il faut poser le problème à l'envers. Qu'est-ce qui est le plus long dans ton algo ? Le parcours de la nouvelle ligne et de la nouvelle colonne dans un carré que tu cherches à agrandir.
Le préremplissage de la matrice contenant au pire 350 * 350 cases = 122500 cases sera quasi instantané. Tu parcours ligne par ligne. A chaque début de ligne ton compteur est remis à zéro. Tant que tu lis un zéro, tu incrémentes le compteur et tu stockes sa valeur dans la case courante puis tu avances d'une case. Si tu trouves un 1, tu remets le compteur à zéro.
Idem pour les colonnes. C'est extrêmement rapide.
Et ceci est à faire une seule et unique fois au début du programme.

Pour la recherche du plus grand carré, pour chaque zéro dans la matrice, tu regarde uniquement le coin en bas à droite, avec 2 tests sur des entiers. Ce sera aussi extrêmement rapide.
En plus, cet algo a l'avantage de la simplicité.

[iakou]

Bonjour.

La méthode est séduisante, hélas je n'arrive pas à interpréter les résultats !

- Pour mieux visualiser j'ai dessiné la matrice 6x7 donnée en exemple, et j'ai mis des cases noires pour les "1" (cases dites 'à moustiques')
- j'ai ensuite appliqué votre méthode, et j'ai donc rempli les cases blanches avec les amplitudes de "0" constatées.

Or je me retrouve avec des incohérences :

- j'ai par exemple une case d'amplitude (2, 2) qui semble dire "carré de 2x2" or c'est faux il comprend une case noire
- ou une case d'amplitude (5, 3) qui semble dire "rectangle de "5x3", alors qu'il ne contient aucun carré de 3x3 sans moustique !.

Il manque quelquechose !...

Cdlt