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

[dinobogan]

C'est un problème de remplissage puis d'interprétation des résultats.
Prenons uniquement le début de la matrice donnée dans le premier post :
1 0 0 1
0 0 0 0
1 0 0 0

Pour chaque zéro, le pré-calcul va ajouter des informations dans les cases contenant des zéros. Le triplet (a,b,c) correspond à :

• a : le zéro,
• b : le nombre de zéros consécutifs à gauche de la case, elle-même incluse
• c : le nombre de zéros consécutifs en haut de la case, elle-même incluse

Voici le contenu du début de matrice :

Code :

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

1
2
3
4
 
1       (0,1,1) (0,2,1) 1
(0,1,1) (0,2,2) (0,3,2) (0,4,1)
1       (0,1,3) (0,2,3) (0,3,2)

Ceci fait, deux boucles "for" vont parcourir la matrice ligne par ligne. Une case "1" est ignorée. Le premier "1" est donc ignoré. Ensuite on trouve un zéro en première ligne, deuxième colonne, l'algo de recherche commence.
Les coordonnées de ce "0" sont (1;0), qu'on appellera CH (pour coin haut). Une boucle for va incrémenter un entier G, qui sera ajouté aux coordonnées de cette case pour agrandir le coin bas droit du carré CB tant que CB contient un zéro.

Première case CB à analyser pour G=1 : CB = (1+G ; 0+G) = (1+1 ; 0+1) = (2;1). Elle contient un zéro, donc on peut analyser ses valeurs "b" pour l'horizontale et "c" pour la verticale :

• horizontal : (b = 3 pour CB) > ( (abscisse CB) - (abscisse CH) = (2 - 1) = 1 ) donc CB est valide pour l'horizontale
• verticale : (c = 2 pour CB) > ( (ordonnée CB) - ( ordonnée CH) = (1 - 0) = 1) donc CB est valide pour la verticale

CB est valide à la fois pour l'horizontale et pour la verticale, donc on valide CB pour G=1

On incrémente G, G=2 : CB = (1 + G ; 0 + G) = (1 + 2 ; 0 + 2) = (3;2). Ce nouveau CB contient les valeurs (0,3,2). Faisons encore une fois la même analyse :

• horizontal : (b=3) > ( (abscisse CB) - (abscisse CH) = 3 - 1 = 2 ) donc CB est valide pour l'horizontale
• verticale : (c=2) n'est pas strictement supérieur à ( (ordonnée CB) - (ordonnée CH) = 2 - 0 = 2 ) donc CB n'est pas valide pour la vertical

CB pour G=2 est valide pour l'horizontal mais pas pour la vertical, donc le plus grand carré partant de CH est pour G=1, soit un carré de 2 cases de côté.

L'algorithme se poursuit en avançant CH, et ainsi de suite.


EDIT : modification des valeurs précalculées dans la matrice (mais pas utilisées dans le reste de l'explication) suite à remarque du post suivant

[iakou]

J'ai compris les données du problème, mais apparemment, ce que vous dîtes et ce que vous faites, divergent :

pour case[I,J] = case[1,1] c'est une case noire, c'est dire avec moustiques. que vous notez 1 (no problem !...)
pour case[I,J] = case[1,2] c'est une case blanche sans moustique que vous notez (0,0,0) or d'apès ce que vous disiez elle devrait être (0,1,1)...
pour case[I,J] = case[1,3] c'est une case blanche sans moustique que vous notez (0,0,0) or d'apès ce que vous disiez elle devrait être (0,2,1)...

Déjà nous ne sommes pas d'accord sur la 1ère ligne.

Ni sur la deuxième ligne où :

pour case[2,1] j'ai de mon coté [1,1], ce qui ne correpond pas à votre notation (0,0,0)

En revanche :
pour case[2,2] je suis d'accord j'ai de mon coté [2,2] qui correpond à votre notation (0,2,2)
pour case[2,3] je suis d'accord j'ai de mon coté [3,2] qui correpond à votre notation (0,3,2)
pour case[2,4] je suis d'accord j'ai de mon coté [4,1] qui correpond à votre notation (0,4,1)

Mais cela ne répond pas à ma question initiale :
Si on prend la case[2,2] d'amplitude 2 en nombre de zéros, elle ne correpond pas à un carré de 2x2 sans moustique !
De même pour la case[3,6] rectangle d'amplitude 5 et 3 (c'est dire longueur= 5 et hauteur= 3) il ne contient aucune carré 3x3 sans moustique.

QUESTION : Une fois votre tableau rempli avec votre méthode. Comment faites-vous pour trouvez le plus grand carré ?.. (vous sembliez dire au départ de votre intervention, qu'une fois ce travail de calcul effectué, tout était fini)


PS: Je comprends mieux la méthode plus naturelle de metralla, (j'ai d'ailleurs un moyen de l'optimiser)

[dinobogan]

J'ai compris les données du problème, mais apparemment, ce que vous dîtes et ce que vous faites, divergent :



Déjà nous ne sommes pas d'accord sur la 1ère ligne.

Ni sur la deuxième ligne où :

Effectivement, j'ai modifié ces cases. Les données étaient incorrectes. La suite de l'explication ne change pas puisque ces données n'étaient pas utilisées.

En revanche :
pour case[2,2] je suis d'accord j'ai de mon coté [2,2] qui correpond à votre notation (0,2,2)
pour case[2,3] je suis d'accord j'ai de mon coté [3,2] qui correpond à votre notation (0,3,2)
pour case[2,4] je suis d'accord j'ai de mon coté [4,1] qui correpond à votre notation (0,4,1)

Mais cela ne répond pas à ma question initiale :
Si on prend la case[2,2] d'amplitude 2 en nombre de zéros, elle ne correpond pas à un carré de 2x2 sans moustique !

Je n'ai pas dit ça. Le précalcul ne permet pas du tout de connaitre déjà le résultat. Le préremplissage permet seulement de compter des zéros sur des lignes et des colonnes, rien d'autre. Il n'y a pas de notion de "carré" dans ce pré-calcul.

De même pour la case[3,6] rectangle d'amplitude 5 et 3 (c'est dire longueur= 5 et hauteur= 3) il ne contient aucune carré 3x3 sans moustique.

Exact, comme expliqué : le pré-calcul ne permet pas de connaitre directement les carrés sans moustiques.

QUESTION : Une fois votre tableau rempli avec votre méthode. Comment faites-vous pour trouvez le plus grand carré ?..

Je ne peux pas détailler plus que ça mon algorithme. J'ai tout dit.

(vous sembliez dire au départ de votre intervention, qu'une fois ce travail de calcul effectué, tout était fini)

Une fois le pré-calcul effectué, il faut faire tourner l'algorithme.

[Jedai]

Pour éclaircir la méthode (pour certains), en voici une implémentation :

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
import Data.Array
import Control.Monad
import Control.Arrow ((&&&))
import Data.Ord
import Data.List
 
type Size = Int
type Pos = (Int,Int)
type Matrix a = Array Pos a
type InitialMatrix = Matrix Int
type WithMinIJ = Matrix (Int, Int, Int)
 
-- Lit une matrice sur stdin
readMatrix :: IO InitialMatrix
readMatrix = do
  [x,y] <- fmap (map read . words) $ getLine
  lines <- replicateM x getLine
  let cells = concatMap (map read . words) lines
  return $ listArray ((1,1),(x,y)) cells
 
-- Annote une matrice
noteMinIJ :: InitialMatrix -> WithMinIJ
noteMinIJ matrix = withMins
  where
    withMins = listArray (bounds matrix) [cell c | c <- assocs matrix]
    cell ((i,j),1) = (1, i+1, j+1)
    cell ((i,j),0) = (0, s3 i (withMins ! (i-1,j)), t3 j (withMins ! (i,j-1)))
    s3 1 _ = 1
    s3 _ (_,i,_) = i
    t3 1 _ = 1
    t3 _ (_,_,j) = j
 
-- "extendSquare mat p" Trouve la taille maximale du carré de 0s constructible à partir du coin haut gauche p
-- dans la matrice annotée mat
extendSquare :: WithMinIJ -> Pos -> Size
extendSquare mat p@(i,j) = until invalidSquare (+1) 0
  where invalidSquare n
          | inRange (bounds mat) (i',j'),
            (0,iM,jM) <- mat ! (i',j'),
            iM <= i, jM <= j                = False
          | otherwise                       = True
          where
            i' = i+n
            j' = j+n
 
-- Position et taille du plus grand carré de 0s dans la matrice
maxSquare :: InitialMatrix -> (Pos, Size)
maxSquare mat = maximumBy (comparing snd) . map (id &&& extendSquare notedMat) $ range (bounds mat)
  where
    notedMat = noteMinIJ mat

Le langage peut être peu familier mais l'idée est là :

• lire la matrice dans un tableau,
• annoter les cases de ce tableau avec la ligne minimale à partir de laquelle on ne trouve que des zéro jusqu'à la case courante sur la colonne, vice-versa pour la colonne minimale. (plus évident en C qu'en Haskell, je recommande de faire simplement deux parcours, un en ligne, un en colonne)
• Prendre avantage de ces annotations pour repérer le carré maximal constructible à partir d'un certain coin haut gauche (comparé à une implémentation naïve, cette opération est en O(côté du carré) au lieu de O(côté²))
• Finalement essayer de construire les carrés maximaux pour toutes les cases et retenir le plus grand.

N'hésiter pas à poser des questions sur le détail de chacune de ces opérations.
--
Jedaï

[foetus]

C'est un problème de remplissage puis d'interprétation des résultats.
Prenons uniquement le début de la matrice donnée dans le premier post :
1 0 0 1
0 0 0 0
1 0 0 0

Pour chaque zéro, le pré-calcul va ajouter des informations dans les cases contenant des zéros. Le triplet (a,b,c) correspond à :

• a : le zéro,
• b : le nombre de zéros consécutifs à gauche de la case, elle-même incluse
• c : le nombre de zéros consécutifs en haut de la case, elle-même incluse

Voici le contenu du début de matrice :

Code :

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

1
2
3
4
 
1       (0,1,1) (0,2,1) 1
(0,1,1) (0,2,2) (0,3,2) (0,4,1)
1       (0,1,3) (0,2,3) (0,3,2)

Un algo ici

Je ne suis pas convaincu par la notion de temps avec ton algo

Par contre, pour l'optimiser (à tester évidement) on peut faire "une liste de priorité" par rapport à max(b, c) et b + c de n > b' + c' de n + 1 en rajoutant (x, y) entre a et b

Ta matrice devient: (0, 3, 1, 4, 1), (0, 2, 1, 3, 2), (0, 2, 2, 2, 3), (0, 3, 2, 2, 3), (0, 1, 2, 1, 3), (0, 1, 1, 2, 2), (0, 2, 1, 2, 1), (0, 1, 1, 1, 1)
Et on s'arrête lorsqu'on a trouvé le premier carré en utilisant ton algo (*): avec (0, 3, 1, 4, 1) cela ne va rien donner.
Par contre avec (0, 2, 1, 3, 2) on devrait trouver un carré de 2x2

* -> Tester l'arrêt pour des cas bananes à définir

[iakou]

Bonjour.
J'ai enfin compris !
Grâce au travail préparatoire, on sait quand on aggrandit le carré en construction, si l'itération qu'on vient de faire est valide ou non.
Le "non-dit" était une évidence, mais apparemment pas pour moi.
Cordialement.