labirinto.cpp

#include "iostream"
#include "vector"
#include "stack"
using namespace std;

vector< vector<bool> > grafo;
vector<bool> visitado;
vector<int> valor;
stack<int> caminho;
int busca;

int getFilho(int pai){
  for(int cont=0;cont<grafo.size();cont++){
    if(grafo[pai][cont]) return cont;
  }
  return -1;
}

void dfs(int atual){
  int filho = getFilho(atual);
  visitado[atual] = true;
  
  if(valor[atual] == busca){ 
    printf("saida encontrada no vertice %d\n",atual);
  
  }else if(filho != -1){
    printf("vai: %d -> %d\n",atual,filho);
    grafo[atual][filho] = false;
    grafo[filho][atual] = false;
    caminho.push(atual);
    dfs(filho);
    
  }else if(!caminho.empty()){
    int pai = caminho.top();
    caminho.pop();
    printf("volta: %d -> %d\n",atual,pai);
    dfs(pai);
  } 
}

int main(void){
  grafo = vector< vector<bool> >({
    {false,true,true},
    {true,false,false},
    {true,false,false},
  });
  
  visitado = vector<bool>(3);
  valor = vector<int>({1,2,3});
  busca = 3;
  dfs(0);
  
  return 0;
}