/*********************/
/*-- correction tp --*/
/*--- mots meles-----*/
/* LG novembre 2004  */
/*********************/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 10
#define VRAI 1
#define FAUX 0
#define bool int


/*********************************************************************/
/*------------------- fonctions non demandées -----------------------*/
/*********************************************************************/

/*tire un entier au hasard entre inf et sup */
int hasard(int inf, int sup)
{
  int rando = rand();
  return (inf + (rando % (sup - inf +1)));
}

/*initialisation au hasard du tableau 2d de caractères et remplissage motif*/
void initialise(char T[N][N], char motif[N+1])
{
  int i,j;
  for (i=0;i<N;i++)
    {
      for (j=0;j<N;j++)
	{
	  T[i][j]= hasard(97,122);
	}
    }
  motif[0]='m';
  motif[1]='a';
  motif[2]='\0';

  T[0][0]='m';
  T[0][1]='a';
  T[0][2]='u';

  /*impression pour voir*/
  for (i=0;i<N;i++)
    {
      for (j=0;j<N;j++)
	{
	  printf("%c ", T[i][j]);
	}
      printf("\n");
    }
}
/*********************************************************************/

void affiche_motif(char motif[N+1])
{
  int i=0;
  while ((motif[i] != '\0') && (i<N+1))
    {
      printf("%c",motif[i]);
      i++;
    }
  
  printf("\n");
}

/*on suppose que le tableau du motif a un marqueur de fin \0*/
bool cherche_gauche_droite(char motif[N], char tab[N][N], int l, int c)
{
  int j=0;
  bool res = FAUX; /*si on sort à cause des bornes, on retourne FAUX*/
  bool continuer = VRAI;

  while (continuer && (j<N) && (c+j<N))
    {
      if (motif[j] == '\0')
	{
	  continuer = FAUX; res  = VRAI;
	}
      else
	{
	  if (motif[j] != tab[l][c+j])
	    {
	      continuer = FAUX; res = FAUX;
	    }
	  else
	    {
	      j++;
	    }     
	}
    }
  return res; 
}

/*dans le même esprit*/
bool cherche_bas_haut(char motif[N], char tab[N][N], int l, int c)
{
  int i=0;
  bool res = FAUX;
  bool continuer = VRAI;

    while (continuer && (i<N) && (l-i>0))
    {
      if (motif[i] == '\0')
	{
	  continuer = FAUX; res  = VRAI;
	}
      else
	{
	  if (motif[i] != tab[l-i][c])
	    {
	      continuer = FAUX; res = FAUX;
	    }
	  else
	    {
	      i++;
	    }     
	}
    }
  return res; 
}

/*diagonale descendante G/D*/
bool cherche_diag1(char motif[N], char tab[N][N], int l, int c)
{
  int k=0;
  bool res = FAUX;
  bool continuer = VRAI;

  
  while (continuer && (k<N) && (c+k<N) && (l+k<N))
    {
      if (motif[k] == '\0')
	{
	  continuer = FAUX; res  = VRAI;
	}
      else
	{
	  if (motif[k] != tab[l+k][c+k])
	    {
	      continuer = FAUX; res = FAUX;
	    }
	  else
	    {
	      k++;
	    }     
	}
    }
  return res; 
}

/*diagonale montante G/D*/
bool cherche_diag2(char motif[N], char tab[N][N], int l, int c)
{
  int k=0;
  bool res = FAUX;
  bool continuer = VRAI;
  
  while (continuer && (k<N) && (l-k>0) && (c+k<N))
    {
      if (motif[k] == '\0')
	{
	  continuer = FAUX; res  = VRAI;
	}
      else
	{
	  if (motif[k] != tab[l-k][c+k])
	    {
	      continuer = FAUX; res = FAUX;
	    }
	  else
	    {
	      k++;
	    }     
	}
    }
  return res; 
}

bool cherche_droite_gauche(char motif[N], char tab[N][N], int l, int c)
{
  int j=0;
  bool res = FAUX; 
  bool continuer = VRAI;

  
  while (continuer && (j<N) && (c-j>0))
    {
      if (motif[j] == '\0')
	{
	  continuer = FAUX; res  = VRAI;
	}
      else
	{
	  if (motif[j] != tab[l][c-j])
	    {
	      continuer = FAUX; res = FAUX;
	    }
	  else
	    {
	      j++;
	    }     
	}
    }
  return res; 
}

bool cherche_haut_bas(char motif[N], char tab[N][N], int l, int c)
{
  int i=0;
  bool res = FAUX;
  bool continuer = VRAI;

    while (continuer && (i<N) && (l+i<N))
    {
      if (motif[i] == '\0')
	{
	  continuer = FAUX; res  = VRAI;
	}
      else
	{
	  if (motif[i] != tab[l+i][c])
	    {
	      continuer = FAUX; res = FAUX;
	    }
	  else
	    {
	      i++;
	    }     
	}
    }
  return res; 
}

bool trouve_motif(char motif[N+1], char T[N][N])
{
  int i,j;
  bool res = FAUX;

  printf("Le motif ");
  affiche_motif(motif);
  printf("apparait ...\n");
  for (i=0;i<N;i++)
    {
      for (j=0;j<N;j++)
	{
	  if (cherche_haut_bas(motif, T, i, j))
	    {
	      res = VRAI;
	      printf("--verticalement de haut en bas à partir de (%d,%d)\n",i,j);
	    }
	  if (cherche_bas_haut(motif, T, i, j))
	    {
	      res = VRAI;
	      printf("--verticalement de bas en haut à partir de (%d,%d)\n",i,j);
	    }
	  if (cherche_gauche_droite(motif, T, i, j))
	    {
	      res = VRAI;
	      printf("--horizontalement de gauche à droite à partir de (%d,%d)\n",i,j);
	    }
	  if (cherche_droite_gauche(motif, T, i, j))
	    {
	      res = VRAI;
	      printf("--horizontalement de droite à gauche à partir de (%d,%d)\n",i,j);
	    }
	  if (cherche_diag1(motif, T, i, j))
	    {
	      res = VRAI;
	      printf("--en diagonale descendante G/D à partir de (%d,%d)\n",i,j);
	    }
	  if (cherche_diag2(motif, T, i, j))
	    {
	      res = VRAI;
	      printf("--en diagonale montante G/D à partir de (%d,%d)\n",i,j);
	    }
	  /*il manque 2 cas*/

	}
    }
  if (!res) {printf("et ben non\n");}
  return res;
}

int main (void)
{
  char T[N][N];
  char motif[N+1];
  bool b;

  srand(time(NULL));

  initialise(T, motif);
  trouve_motif(motif,T);

  return 0;
}