Blocage exercice C

Version imprimable

Blocage exercice C

Bonjour, je suis étudiant en 1 ère année dans une école d'informatique et j'ai un projet à rendre pour bientôt dans lequel je bloque complètement, il s'agit du BSQ..
Ce projet consiste a trouver, dans une map donnée : exemple :
.....o..
.o......
.o...o.o
.o......
.....o..
.oo...o.
.o.o....
..o.....
Le plus grand CARRE dans cette map et le remplacer par des X comme ceci :
.....o..
.oXXX...
.oXXXo.o
.oXXX...
.....o..
.oo...o.
.o.o....
..o.....

Alors voila j'ai récupérer la map dans un buffer puis ensuite je l'ai stocké dans un tableau à 2 dimensions pour facilité la recherche. Mais l'algorithme de recherche je ne le comprend pas, du moins je ne vois pas du tout comment le coder si ce n'est avec 5678 variables peut être et encore ... J'ai vu qu'il y avait une méthode qui consistait à partit d'un point qui serait le coté haut/gauche de mon carré et ensuite de descendre et étendre par la droite mais je ne vois pas comment je peux crée ça avec les while et les if, vraiment pas...
( ah oui je précise que j'ai stocké dans un tableau de int à double entrée mais cela ne change pas grand chose de toute manière..
Voila mon ébauche de code et je suis donc dans la fonction algo qui doit crée la recherche ... =>

En espérant une aide, merci et bonne journée..

Code:

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
 
int             bsq(char *filepath, int my_size)
{
  int           fd;
  char          *str;
  char          buffer[my_size];
  int           r;
  int           cpt;
  int           column;
  int           lane;
 
  str = malloc(my_size * sizeof(char));
  fd = fs_open_file(filepath);
  while ((r = read(fd, buffer, my_size)) > 0)
    {
      column = cpt_column(buffer, cpt, column);
      lane = cpt_lane(buffer, cpt, lane);
      if (r != 0)
        {
          buffer[r] = 0;
          my_strcat(str, buffer);
        }
    }
  buff_in_int(buffer, column, lane);
  /* printf("%c", '\n'); */
  /* printf("%c", '\n'); */
  /* printf("%c", '\n'); */
  printf("%s", str);
  close(fd);
  return (0);

Le stockage du buffer dans le tableau :

Code:

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
 
void            buff_in_int(char *buffer, int column, int lane)
{
  int           tab_int[lane][column];
  int           cpt;
  int           a;
  int           b;
  int           dim;
 
  a = 0;
  b = 0;
  cpt = 0;
  dim = 0;
  while (buffer[a] != '\n') // je met a la 2eme ligne                                        
    a = a + 1;
  a = a + 1;
  while (b != lane - 1) // on crée notre tableau de int                                      
    {
      while (cpt != column)
        {
          if (buffer[a] == '.')
            tab_int[b][cpt] = 0;
          else if (buffer[a] == 'o')
            tab_int[b][cpt] = 1;                                                             
          a = a + 1;
          cpt = cpt + 1;
        }
      a = a + 1;
      cpt = 0;
      b = b + 1;
    }
  algo(column, lane, tab_int);
}

Mon compteur de ligne et de colonne :

Code:

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
 
int             cpt_lane(char *buffer, int cpt, int lane)
{
  lane = 0;
  cpt = 0;
  while (buffer[cpt] != '\0')
    {
      if (buffer[cpt - 1] == '\n')
        lane = lane + 1;
      cpt = cpt + 1;
    }
  return (lane);
}
int             cpt_column(char *buffer, int cpt, int column)                                
{
  cpt = 0;
  column = 0;
  while (buffer[cpt] != '\n')
    cpt = cpt + 1;
  while (buffer[cpt + 1] != '\n')
    {
      column = column + 1;
      cpt = cpt + 1;
    }
  return (column);
}

Puis l'algo ... :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
int             algo(int column, int lane, int tab_int[lane][column])
{
  int           cpt;
  int           cpt2;
  int           cpt3;
  int           a;
 
  a = 0;                                                                                     
  cpt = 0;
  cpt2 = - 1;
  cpt3 = 0;
  while (cpt < column)
    {
      if (tab[a][cpt] == 0)
        {
 
        }
      cpt = cpt + 1;
    }
}

17/12/2015, 16h19
Matt_Houston
Tu devrais peut-être écrire ton algo en français, au calme, sur un morceau de papier au lieu d'imaginer déjà sa transcription en C. C'est plus une question pour la section algorithmique.

Voici la façon dont j'aborderais le problème si j'y étais confronté :
1. on part d'un coin de la matrice ;
2. c'est pour l'instant le plus grand carré qu'on ait trouvé (1x1, forcément il répond aux critères), on stocke ses coordonnées (x_min <- 0, x_max <- 1, y_min <- 0, y_max <- 1) et la valeur qu'il contient ;
3. on étend le carré en ajoutant 1 à ses côtés tant qu'il contient uniquement cette valeur, en mettant à jour le set de coordonnées à chaque itération ;
4. on revient à l'étape 1 en partant cette fois du point (x_max, 0), si x_max est égal à la largeur de la matrice, on part du point (0, y_max) ;
5. on s'arrête :
  - soit lorsqu'il n'est plus possible, dans l'aire restant à traiter, de caser un plus grand carré que le carré actuellement stocké ;
  - soit lorsque x_max = largeur et y_max = hauteur.
17/12/2015, 16h24
rubisom

Bonjour,

Merci de ta réponse !
J'ai déjà essayer de le poser sur papier mais je vais retenter une nouvelle fois..
J'avais déjà penser à cette idée d'etendre le carré en partant du point en haut a gauche donc il suffit de lui dire tant qu'il y a un point a X colonnes et X lignes continue.. Mais ce qui me bloque c'est (par exemple pour un carré de 2 x 2)
On lui dit avance en x + 1 et en y + 1, super il y a des points ! Ce qui nous ferait par exemple :

XX.........
X...........
.............

Mais comment vérifie t'on qu'il n'y est pas d'obstacles alors en coordonné (1,1) (le coté en bas a droite) et vice versa pour le 3x3, 4x4 etc ??.. C'est surtout ça que je n'arrive pas à comprendre.

Mmm... je ne connais pas l'algorithme dont tu parles. Si tu es pressé et veux faire du vite fait pas optimisé, je peux te proposer cela:

1) faire une fonction pour voir si un carré de côté c est possible au coordonnées x, y dans le tableau:
Code:

1 2 3 4 5 6 7 8 9 int does_fit(int x, int y, int s, const int tab** t, int m, int n) // le tableau est de dimension m*n { int cm, cn; if (m < x+s || n < y+s) return 0; // si on déborde du tableau for (cm = x; cm < x+s; ++cm) for (cn = y; cn < y+s; ++cn) if (tab[cm][cn] != 0) return 0; return 1; }
2) utilise cette fonction sur le coin supérieur gauche sur chaque case, en agrandissant à chaque fois. Une fois le carré le plus grand obtenu pour la première case, tu ne testes que les carrés plus grands sur les autres cases à cibler. Déterminer les autres cases à cibler est le point le plus difficile.

A) Tu peux faire force brute et tester toutes les cases, ça ne prendra de toute façon que quelques milisecondes tant que le rectangle d'accueil est de taille raisonnable:
Code:

1 2 3 4 5 6 7 8 9 10 11 void max_possible(const int tab** t, int m, int n, int* x, int* y, int* s) // les trois derniers int pour stocker le résultat: coordonnées angle supérieur et taille { int tmpmax = 0, tmpx = 0, tmpy = 0; int ix, iy; for (ix = 0; ix < m; ++ix) for (iy = 0; iy < n; ++iy) { while (does_fit(ix, iy, tmpmax, tab, m, n)) { ++tmpmax; tmpx = ix; tmpy = iy; } } *x = tmpx; *y = tmpy; *s = --tmpmax; }
B) Une première optimisation simple est de raccourcir la boucle en diminuant les limites de la taille du plus grand carré déjà obtenu: au delà, les carrés obtenus seront nécessairement plus petits:
Code:

1 2 3 4 5 6 7 8 9 10 11 void max_possible(const int tab** t, int m, int n, int* x, int* y, int* s) // les trois derniers int pour stocker le résultat: coordonnées angle supérieur et taille { int tmpmax = 0, tmpx = 0, tmpy = 0; int ix, iy; for (ix = 0; ix < m-tmpmax; ++ix) // on enlève à la boucle la taille du plus grand carré obtenu for (iy = 0; iy < n-tmpmax; ++iy) { // idem while (does_fit(ix, iy, tmpmax, tab, m, n)) { ++tmpmax; tmpx = ix; tmpy = iy; } } *x = tmpx; *y = tmpy; *s = --tmpmax; }
C) à toi de jouer pour d'autres optimisations, mais il faut déjà plus réfléchir...

PS: je n'ai pas testé mon code, il peut y avoir des petites erreurs à corriger

17/12/2015, 17h10
rubisom

Bonjour,

Je n'ai pas tout à fait compris le code car je n'ai pas la droit d'utiliser la boucle for et je ne vois pas dans la première fonction a quoi correspond la variable s.
Je vais essayer de m'y attardé un peu plus longtemps.. Merci

( PS : Les tests qui vont passés sur le programme peuvent avoir une map très très grande mais je ne veux pas de l'optimisation pour le moment de toute manière..)

tu n'as pas le droit d'utiliser la boucle for!!! quelle drôle d'idée!
enfin l'équivalent avec while est juste un peu plus lourd:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int does_fit(int x, int y, int s, const int tab** t, int m, int n) // le tableau est de dimension m*n
{
  int cm, cn;
  if (m < x+s || n < y+s) return 0; // si on déborde du tableau
  cm = x;
  while (cm <  x+s) {
    cn = y;
    while (cn < y+s) {
      if (tab[cm][cn] != 0) return 0;
      ++cn;
    }
    ++cm;
  }
  return 1;
}

s pour size, la taille / le côté du carré

17/12/2015, 17h36
rubisom

Merci de vous donner du mal pour mon problème mais je ne vois définitivement toujours pas comment faire pour trouver le plus grand carré avec les ressources que j'ai et que vous m'avez donné.. Je ne vois pas la logique pour vérifier qu'on à bien un carré,..
comme cité plus haut par exemple si on a un point a tel endroit, on avance en x et en y, il y a des points super, on avance encore une fois donc on arrive la (pour exemple ):

XXX....
X.......
X........

mais la après tout m'échappe pour vérifier s'il y a bien des points au lieu des obstacles aux endroits ici en rouge :
XXX....
XXX.....
XXX......

Je pense abandonner le projet je suis démoralisé c'est la première fois que je bloque vraiment sur un algorithme dont j'ai plus ou moins la logique... Désolé de vous avoir fait perdre du temps..

Bon je persévère encore un peu j'ai essayer de coder quelque chose asser tordu donc je vous ai mis des indications... Je le fais tourner a la main point par point avec pour exemple :

.....o..
.o......
.o...o.o
.o......
.....o..
.oo...o.
.o.o....
..o.....

Donc voila il y a encore pas mal de soucis que je n'arrive pas à reglé, et surtout, le fait de "sauvegarder/afficher les X" pour le plus grand carré... Pour le moment l'algo que je fais ne fait que se déplacer mais de carré en carré (plus ou moins...) J’espère que vous comprendrez le code...

Code:

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
 
int             algo(int column, int lane, char tab_char[lane][column])
{
  int           x;
  int           y;
  int           z;
  int           cpt;                                                                                                                                                                                                                                                                                                        
 
  x = 0;
  y = 0;
  z = 0;
  cpt = 0;
  while (y < lane) // jusqu'a la fin de mes lignes                                                                                                                                                                                                                                                                          
    {
      while (x < column) // jusqu'a la fin de mes colonnes                                                                                                                                                                                                                                                                  
        {
          while (tab_char[y][x] == '.') // tant qu'on trouve un "."                                                                                                                                                                                                                                                         
            {
              while (tab_char[y][x + 1] == '.' && tab_char[y + 1][x] == '.') // si sur le coté droit et juste en dessosu on a un point on descend en bas a droite du carré                                                                                                                                                  
                {
                  x = x + 1;
                  y = y + 1;
                  cpt = cpt + 1;
                }
              while (cpt != 0) // si on tombe sur un 'o' on remonte a notre ligne de depart a l'aide d'un compteur                                                                                                                                                                                                          
                {
                  y = y - 1;
                  cpt = cpt - 1;
                }
              if (cpt == 0 && tab_char[y][x + 1] == 'o') // du bidouillage pour avancer...                                                                                                                                                                                                                                  
                x = x + 1;
            }
          if (tab_char[y][x] == 'o') // si on rencontre un 'o' et non un '.' on avance, mais si on en est sortit a Y lignes, on remonte a notre ligne d'origine a l'aide de compteur                                                                                                                                        
            {
              if (cpt == 0)
                x = x + 1;
              while (cpt != 0)
                {
                  y = y - 1;
                  cpt = cpt - 1;
                }
            }
        }
      y = y + 1; // dès que j'ai fini mes colonnes, je descend d'une ligne et je réinitialise pour repartir de la gauche;.                                                                                                                                                                                                  
      x = 0;
    }
  my_putchar('\n');
}

17/12/2015, 19h24
rubisom

Je reconnais l'immonderie du code par ailleurs..