/**
title: variante dum problema do CeNPL'01: "Apanha Moedas num Labirinto" (proposta extra-aula)
ficheiro: cnpl03.c autor: PRH versao de: 2001.05.06
.uso de arrays multiplos para implementar matrizes, ou tabuleiros
.resoluç~ao recursiva de problemas por "try-and-error"
**/  
#include <stdio.h>
 
#define true 1
#define false 0
typedef int bool;

#define MAXL 9
#define MAXC 5
#define Moedas 7
#define InicL 5
#define InicC 4
/* #define InicC 3 */

typedef int tTabuleiro[MAXL][MAXC];
typedef int tProxMove[4];

tProxMove   IncrL={-1,0,+1,0};
tProxMove   IncrC={0,-1,0,+1};

tTabuleiro  Tab={{0,0,0,0,-1},
                 {-1,0,0,0,0},
                 {0,0,0,-1,0},
                 {0,-1,0,0,0},
                 {0,0,0,0,0},
                 {0,-1,0,0,0},
                 {0,0,0,0,0},
                 {0,0,-1,0,0},
                 {0,0,0,0,-1}
                };

bool valido( int i, int j ){ 
    return( (i>=0)&&(i<MAXL)&&(j>=0)&&(j<MAXC)&&(Tab[i][j]<=0) );
}
    
bool comeMoedas( int i, int j, int m, int vez ){ 
    int ant, tenta;
    int i1, j1;
    bool suc;
    
    if ( Tab[i][j]==-1 ) { m--; }
    ant=Tab[i][j]; Tab[i][j]=vez++;
    if ( m==0 ) 
       { suc=true; }
    else 
       { suc=false; 
         tenta=0; 
	 while (( tenta < 4 )&&( !suc ))
          { i1=i+IncrL[tenta]; j1=j+IncrC[tenta];
            if ( valido(i1,j1) ) 
                 { suc=comeMoedas(i1,j1,m,vez); }
            tenta++;
           }
         if (!suc) Tab[i][j]=ant;
        }
    return( suc );
}

/*----- programa principal -----*/  
int main( )
{ int i,j,conta=0; 

  if (comeMoedas( InicL, InicC, Moedas, 1 ) )
       { printf("Terminou com Sucesso \n"); 
         for(i=0; i<MAXL; i++)
            { for(j=0; j<MAXC; j++) { printf("%2d ",Tab[i][j]); }
              printf("\n");
            }
       }
  else { printf("Nao Conseguiu Terminar com Sucesso \n"); }
  return(0); 
}