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

/**********************************************************
   Exemplo de uso de recursão para achar o caminho num 
   labirinto, seguindo o roteiro mostrado em sala (ver
   apresentação).
**********************************************************/

/**  'tamanho' do labirinto' **/
#define SIZE 8

/** coordenadas do 'destino' **/
#define DI 6
#define DJ 6

char m[SIZE][SIZE];

/***************************************
   Define os valores da matriz que representa
   o labirinto
***************************************/
void inicia(){
  int i,j;
  for(i=0; i < SIZE; i++)
    for(j=0; j < SIZE; j++) m[i][j] = ' ';
  for(i=0; i < SIZE; i++){
    m[i][0] = '#';
    m[i][7] = '#';
    m[7][i] = '#';
    m[0][i] = '#';
  }
  for(i=0; i < SIZE-2; i++){
    m[2][i] = '#';
    m[4][i+2] = '#';
  }
  m[SIZE-3][2] = '#';
  m[SIZE-3][4] = '#';        
}    

void imprime(){
  int i,j;
  for(i=0; i < SIZE; i++){
    for(j=0; j < SIZE; j++) printf("%c",m[i][j]);
    printf("\n");
  } 
  printf("\n");        
}    

/** deslocamentos de cada célula vizinha em relação a esta **/
int  dx[8] = { -1,   -1, -1,  0,  0,   1,  1,  1 };
int  dy[8] = { -1,    0,  1,  -1, 1,  -1,  0,  1 };

/*****************************************
  Tenta ocupar a posição [i][j] e se 
  possível, avança recursivamente para 
  cada uma das posições visinhas.
*****************************************/
void tenta(int i, int j, char ch){
  int k;
  if(m[i][j] == ' '){       /** célula[i][j] está vazia ? **/      
    m[i][j] = ch;           /** sim, marca célula [i][j]  **/
    if((i==DI) &&(j==DJ)) { /** chegou à célula destino ? **/
        imprime();          /** sim, escreve a solução    **/
    } else {                /** não chegou ao destino, tentar na vizinhança **/
      for(k=0; k < 8; k++) tenta(i+dx[k],j+dy[k],ch);
    }
    m[i][j] = ' ';          /** desmarca a célula [i][j] **/
  }    
}    

int main(int argc, char *argv[])
{
  inicia();
  tenta(1,1,'*');
  system("PAUSE");	
  return 0;
}