I  

/*  (a) 
*/

/* --- définition du type des grilles de mots croisés --- */

#define MAX_DIM 100

typedef struct { int N; int M; char contenu_case[MAX_DIM][MAX_DIM]; } grille; 

/* Une grille est définie par :
   - ses dimensions N x M avec 1<=N<=MAX_DIM, 1<=M<=MAX_DIM 
   - le contenu de ses cases : pour i,j | 0<=i<=N-1 et 0<=j<=M-1 
     contenu_case[i][j] représente le contenu de la case (i+1,j+1) càd : 
      - soit un caractère entre 'A' et 'Z' qui représente une lettre
      - soit le caractère '#' qui représente une case noire
*/

int hauteur(grille g)
     /* largeur d'une grille de mots croisés */
{
  return g.N;
}

int largeur(grille g)
     /* hauteur d'une grille de mots croisés */
{
  return g.M;
}

char contenu_case(grille g,int i,int j)
     /* contenu de la case repérée par i et j d'une grille de mots croisés */
     /* i est le numéro de ligne de la case */
     /* j est le numéro de colonne de la case */
     /* pré-condition : 1<=i<=largeur(g) && 1<=j<=hauteur(g) */
{
  return g.contenu_case[i-1][j-1];
}

/* (b) 
*/

int nb_cases_noires_en_ligne(grille g,int i)
     /* retourne le nombre de cases noires sur la ligne i */
{
  int j; /* numéro de colonne pour parcourir la ligne i */
  int r=0; /* résultat (initialement 0) */

  for(j=1;j<=largeur(g);j++) /* parcours de la ligne i */
    if(contenu_case(g,i,j)=='#') /* si la case courante est une case noire */
      r++; /* on incrémente r */
  return r; /* le résultat est la valeur finale de r */
}

/* (c) 
*/
void affiche_nb_lettres_en_ligne(grille g,int i)
     /* affiche le nombre de lettres entre chaque case noire sur la ligne i */
{
  int j; /* numéro de colonne pour parcourir la ligne i */
  int j0=1; /* numéro de colonne de la première lettre d'un groupe (initialement 1) */

  for(j=1;j<=largeur(g)+1;j++) /* parcours de la ligne i */
    if(j>largeur(g) || contenu_case(g,i,j)=='#') /* si la case courante est une case noire */
      {
      printf("%d ",j-j0); /* le nombre de lettres du groupe est la différence j-j0 */
      j0=j+1; /* on met à jour j0 pour le prochaine groupe de lettres */
      }   
  printf("\n");
}

II  

/* (a) 
*/
void affiche_nb_lettres_de_mot_en_ligne(grille g,int i)
     /* affiche le nombre de lettres entre chaque case noire sur la ligne i */
{
  int j; /* numéro de colonne pour parcourir la ligne i */
  int j0=1; /* numéro de colonne de la première lettre d'un groupe (initialement 1) */

  for(j=1;j<=largeur(g)+1;j++) /* parcours de la ligne i */
    if(j>largeur(g) || contenu_case(g,i,j)=='#') /* si la case courante est une case noire */
      {
      if(j-j0>1) printf("%d ",j-j0); /* si c'est un mot, on affiche son nombre de lettres */
      j0=j+1; /* on met à jour j0 */
      } 
  printf("\n");
}

/* (b) 
*/
int nb_mots_en_ligne(grille g,int i)
     /* retourne le nombre de mots sur la ligne i */
{
  int j; /* numéro de colonne pour parcourir la ligne i */
  int j0=1; /* numéro de colonne de la première lettre d'un groupe (initialement 1) */
  int r=0; /* résultat (initialement 0) */

  for(j=1;j<=largeur(g)+1;j++) /* parcours de la ligne i */
    if(j>largeur(g) || contenu_case(g,i,j)=='#') /* si la case courante est une case noire */
      {
      if(j-j0>1) r++; /* si on a un groupe d'au moins 2 lettres, on compte un mot de plus */
      j0=j+1; /* on met à jour j0 */
      }
  return r; /* le résultat est la valeur finale de r */
}

/* (c) 
*/

void affiche_mots_en_ligne(grille g,int i)
     /* affiche chacun des mots sur la ligne i */
{
  int j; /* numéro de colonne pour parcourir la ligne i */
  int j0=1; /* numéro de colonne de la première lettre d'un groupe (initialement 1) */
  int k; /* compteur sur les lettres d'un mot */

  for(j=1;j<=largeur(g)+1;j++) /* parcours de la ligne i */
    if(j>largeur(g) || contenu_case(g,i,j)=='#') /* si la case courante est une case noire */
      {
      if(j-j0>1) /* si on a un groupe d'au moins 2 lettres */
        {
          /* affichage de chacune des lettres du mot */
          for(k=j0;k<j;k++)
            printf("%c",contenu_case(g,i,k));
          printf(" ");          
        }
      j0=j+1; /* on met à jour j0 */
      }
  printf("\n");
}

/* (d)
 */

// "affiche_mots_en_colonne" s'obtient à partir de "affiche_mots_en_ligne"
//   en effectuant les remplacements suivants :
//   - contenu_case(g,i,j) ==> contenu_case(g,j,i) 
//   - largeur(g) ==> hauteur(g)

void solution_grille(grille g)
     /* affiche la solution d'une grile de mots croisés */
{
  int i; /* numéro de ligne */
  int j; /* numéro de colonne */

  /* pour chaque ligne, affichage des mots sur la ligne */
  printf("Horizontalement :\n");
  for(i=1;i<=largeur(g);i++) 
    affiche_mots_en_ligne(g,i);

  /* pour chaque colonne, affichage des mots sur la colonne */
  printf("Verticalement :\n");
  for(j=1;j<=hauteur(g);j++)
    affiche_mots_en_colonne(g,j);
}

III  

/* (a) 
*/

void nieme_mot_en_colonne(grille g,int j, int n, char mot[])
     /* extrait le nième mot sur la colonne j */
{
  int i; /* numéro de ligne pour parcourir la colonne j */
  int i0=1; /* numéro de ligne de la première lettre d'un groupe (initialement 1) */
  int k; /* compteur sur les lettres d'un mot */
  int nb_mots=0; /* nombre de mots rencontrés sur la colonne (initialement 0) */

  mot[0]='\0';

  for(i=1;i<=hauteur(g)+1;i++) /* parcours de la colonne j */
    if(i>hauteur(g) || contenu_case(g,i,j)=='#') /* si la case courante est une case noire */
      {
      if(i-i0>1) /* si on a un groupe d'au moins 2 lettres */
        {
          /* affichage de chacune des lettres du mot */
          nb_mots++;
          if(nb_mots==n)
            {
            for(k=i0;k<i;k++)
              mot[k-i0] = contenu_case(g,k,j);
            mot[k-i0]='\0';
            }          
        }
      i0=i+1; /* on met à jour i0 */
      }
}

/* (b) 
*/

// "nb_mots_en_colonne" s'obtient à partir de "nb_mots_en_ligne" 
// en effectuant les remplacements suivants :
// - contenu_case(g,i,j) ==> contenu_case(g,j,i) 
// - largeur(g) ==> hauteur(g)                                       

/* --- définition du type des booléens */

typedef int bool;

#define vrai 1
#define faux 0

bool est_vertical(grille g, char mot[])
     /* détermine si le mot est placé verticalement dans la grille */
{
  int j; /* numéro de colonne pour parcourir la colonne j */
  int n; /* position d'un mot sur la colonne j */
  bool trouve = faux; /* résultat (initialement faux) */
  char mot_trouve[MAX_DIM+1];

  for(j=1;j<=hauteur(g);j++) /* parcours des colonnes */
    for(n=1;n<=nb_mots_en_colonne(g,j);n++) /* parcours des mots sur chaque colonne */
      {
      nieme_mot_en_colonne(g,j,n,mot_trouve);
      trouve = trouve || (strcmp(mot,mot_trouve)==0); 
      }
      /* trouvé est à vrai dés que l'on a trouvé le mot */

  return trouve;
}

This document was translated from L^AT_EX by H^EV^EA.