Exercice case accessibles

Version imprimable

20/06/2008, 17h49
crow56

Exercice case accessibles

Bonjour,

je fais cet exo :

mais le problème est que je ne n'arrive pas à détecter les cases accessibles.

En fait, j'ai pensé à faire cela :
compter le nombre de cases accessibles puis de faire la soustraction entre le nombre de cases et de cases accessibles pour enfin avoir le nombre de cases inaccessibles, ce qui me semble la meilleure solution, à mon avis.

Mais quelle est la méthode pour compter les cases accessibles ?

Merci.
20/06/2008, 20h40
Aldian

Bonjour

La solution est tout simplement d'utiliser un tableau (suivant le principe de la file) qui au départ ne contient que la case d'entrée du labyrinthe.

Ensuite tu fais une boucle qui fait ceci :

tant qu'il y a encore des cases dans la file,

prendre la première case de la file, répertorier les cases libres qui sont autour et qui n'ont pas déjà été ajoutées à la file, les ajouter au bout de la file, et incrémenter un coup le compteur qui indique quelle est la première case de la file.

Quand la boucle s'arrête, le compteur indique le nombre de cases répertoriées. C'est également le nombre que tu recherches :D
21/06/2008, 02h12
crow56

je ne connais pas le principe de la file, et je n'ai pas compris le principe.
Est-ce qu'il existe une autre méthode ?
21/06/2008, 15h40
Emmanuel Delahaye

Citation:

Envoyé par crow56

je ne connais pas le principe de la file, et je n'ai pas compris le principe.
Est-ce qu'il existe une autre méthode ?

Ce genre d'exercice est fait pour te faire progresser, alors c'est le moment de se plonger dans les articles qui parlent des structures de données. Il y en a sur ce site et sur le web...

voilà mon 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
 
#include <stdio.h>
 
const int MAX_COLS = 1000;
const int MAX_LIGS = 1000;
 
int main()
{
   int nbLigs, nbCols;
   int count = 0;
   scanf("%d%d", &nbLigs, &nbCols);
   for (int curLig = 0; curLig < nbLigs; curLig++)
   {
      char ligneLue[MAX_COLS+1][MAX_LIGS+1];
      scanf("%s", ligneLue);
      for (int curCol = 0; curCol < nbCols; curCol++)
      {
      	if (ligneLue[curCol][curLig] == '.')
      	{
      		if ( (ligneLue[curCol+1][curLig] == '.' && ligneLue[curCol-1][curLig] == '.')
      			|| (ligneLue[curCol][curLig+1] == '.' && ligneLue[curCol][curLig-1] == '.') )
      		{
      			count++;
      		}
      	}
      }
 
 
   }
   printf("%d\n", count);
   return 0;
}

mais il ne fonctonne pas, est-ce que vous pouvez me le corriger, svp ?

Merci.

Citation:

Envoyé par crow56

voilà mon code :
<...>
mais il ne fonctonne pas, est-ce que vous pouvez me le corriger, svp ?

Merci.

Code:

1
2
3
4
5
6
7
8
9
10
11
 
-------------- Build: Debug in hello ---------------
 
Compiling: main.c
C:\dev\hello\main.c:7: warning: function declaration isn't a prototype
C:\dev\hello\main.c: In function `main':
C:\dev\hello\main.c:14: warning: char format, different type arg (arg 2)
Linking console executable: bin\Debug\hello.exe
Output size is 18.77 KB
Process terminated with status 0 (0 minutes, 1 seconds)
0 errors, 2 warnings

Citation:

Code:

1
2
3
 
         char ligneLue[MAX_COLS + 1][MAX_LIGS + 1];
         scanf ("%s", ligneLue);

Ceci n'a aucun sens. Que cherches-tu à faire ?

22/06/2008, 17h58
crow56

en fait, pour une case libre, que faut-il vérifier ?
j'ai pensé qu'il faut que autour de la case, il faut que ça soit des cases libres, mais je n'en suis pas sûr.

Quel est le principe de l'algo (pseudo-code), pour cet exo ?
25/06/2008, 19h45
Aldian

Je vais détailler un peu plus (je ne connais pas le pseudo code standar, mais tu devrais comprendre)

/*initialisation*/
case tableau[NBCASESMAX];
int pointeur_debut_file=0;
int pointeur_fin_file=1;
tableau[0]=sortie_labyrinthe;

/*boucle*/
while (pointeur_fin_file>pointeur_debut_file)
{
case_en_cours=tableau[pointeur_debut_file];
si case_de_gauche existe

si case_de_gauche 'pas dans tableau'
{tableau[pointeur_fin_file]=case_de_gauche;
pointeur_fin_file++;}

'idem case_du_dessus'
'idem case_du_dessous'
'idem case_de droite'
pointeur_debut_file++;
}
printf("Nombre de cases accessibles: %d\n",pointeur_fin_file);

A part ça les déclarations se font en dehors des boucles. Par ailleurs si tu ne lis qu'une seule ligne du labyrinthe (avec ton scanf), rentre là dans un tableau de une dimension, ça marchera mieux. Sauf que du coup comme tu rentre tes lignes une par une, tu ne peux pas trouver les cases accessibles de la ligne du dessous avant d'avoir rentré cette ligne. En bref il va falloir que d'abord tu fasses une fonction char **charge(void) qui va te charger ton labyrinthe dans un tableau de caractères et ensuite seulement tu pourras exécuter dessus un algorithme de recherche des cases libres. Mais mélanger les deux me parait risqué..