#include <stdio.h>
#define NP 6
#define MP 5

/**********************************************
   Exemplo de uso de recursão para resolver o 
   problema proposto no lab01. Usa o mesmo método
   usado no programa para encontrar o caminho num
   labirinto (ver apresentação sobre funções 
   recursivas).
***********************************************/

/** 'mapa': indica se existe caminho da ilha i para a ilha j **/
int caminho[][6] = {
                      /* partida */ { 0, 1, 1, 0, 0, 0 },
                      /*  ilha 1 */ { 0, 0, 0, 1, 1, 0 },
                      /*  ilha 2 */ { 0, 0, 0, 1, 1, 0 },
                      /*  ilha 3 */ { 0, 1, 1, 0, 1, 1 },
                      /*  ilha 4 */ { 0, 1, 1, 1, 0, 1 },
                      /*  ilha F */ { 0, 0, 0, 0, 0, 0 }
                   };
                   
char* nomes[] = { "P", "1", "2", "3", "4", "F "};  // nomes das ilhas
                  
/** dados para teste (do enunciado) **/
int q1[] = { 0,   50,  150,   50, 200, 0 }, lim1 =  350;
int q2[] = { 0, 3105, 2350, 1640, 320, 0 }, lim2 = 3650;

/** 'caminho atual'  **/
int ca[NP]; // sequência de 'passos' da origem até a ilha atual
int va;     // quantidade de $$ acumulada no 'caminho atual'

/** jv mantém as ilhas já visitadas **/
int jv[] = { 0, 0, 0, 0, 0, 0 };

/** o melhor caminho **/
int mk = 0;      // tamanho do melhor caminho
int vmax = 0;    // valor $$ acumulado
int mc[NP];      // passos (ilhas) do melhor caminho

/** ditto **/
void escreveCaminho(int k, int c[], int v){
     int i;
     printf("tesouro:%d  caminho: ",v);
     for(i = 1; i <= k; i++) printf("%s, ",nomes[c[i]]);
     printf("\n");
}
     
/***
      tenta avançar no caminho até o destino                   
            k: número de ilhas já visitadas
            q: indica a quantidade de $$ por ilha
            lim: capacidade máxima do navio
***/
void tenta(int k, int q[], int lim){
   int j;
   int ia = ca[k-1]; // ilha atual
   // podemos chegar ao destino ? 
   if(caminho[ia][NP-1]){ 
      // este é o melhor caminho até agora ?
      if(va > vmax){
         // sim, então atualiza o melhor caminho
         mk = k;        // n. passos
         vmax = va;     // valor $$
         for(j = 0; j < k; j++) mc[j] = ca[j];  // copia os passos do caminho atual
         mc[k] = NP-1;  // e diz que chega ao destino ...
      }
   }
   for(j = 1; j < (NP-1); j++){
      // a ilha j é viável ?   
      if((!jv[j]) && caminho[ia][j] && ((va + q[j]) <= lim )){
          jv[j] = 1;  // ilha visitada
          va += q[j]; // acumula carga
          ca[k] = j;  // coloca a ilha j no caminho atual
          tenta(k+1,q,lim); // tenta ir adiante
          jv[j] = 0;  // desmarca ilha e
          va -= q[j]; // devolve a carga
      }
   }  
}

int main(){
    ca[0] = 0;
    va = 0;
    tenta(1,q1,lim1);      
    //tenta(1,q2,lim2);    
    //tenta(1,q1,9999999);
    escreveCaminho(mk,mc,vmax);
    system("PAUSE");
}