.cpp

#include <string>

using namespace std;

//usando uma matriz de caracteres para representar o labirinto
//'p' = parede, 's' = saida, 'v' = visitado

void caminhar(Grafo, linha, coluna, percursoAtual) {
     percursoAtual = "(" + to_string(linha) + "," + to_string(coluna) + ")"; //adicionamos o quadrado atual ao percursoAtual
     if (Grafo[linha][coluna]=='s') { //se estamos no quadrado de término (saída), acabou: sucesso!
          cout << "Encontramos a saída, caminho: " << percursoAtual << "\n"; //imprimimos o caminho seguido
     } else {
          Grafo[linha][coluna] = 'v'; //estamos visitando este quadrado do labirinto
          
          int proxLinha, proxColuna;

          //vizinho a esquerda
          proxLinha = linha; proxColuna = coluna-1; 
          if (Grafo[proxLinha][proxColuna] != 'p' && Grafo[proxLinha][proxColuna] != 'v') {
            caminhar(Grafo, proxLinha, proxColuna, percursoAtual);
          }
       
          //vizinho a direita
          proxLinha = linha; proxColuna = coluna+1; 
          if (Grafo[proxLinha][proxColuna] != 'p' && Grafo[proxLinha][proxColuna] != 'v') {
            caminhar(Grafo, proxLinha, proxColuna, percursoAtual);
          }
       
          //vizinho a cima
          proxLinha = linha-1; proxColuna = coluna; 
          if (Grafo[proxLinha][proxColuna] != 'p' && Grafo[proxLinha][proxColuna] != 'v') {
            caminhar(Grafo, proxLinha, proxColuna, percursoAtual);
          }
       
          //vizinho a baixo
          proxLinha = linha+1; proxColuna = coluna; 
          if (Grafo[proxLinha][proxColuna] != 'p' && Grafo[proxLinha][proxColuna] != 'v') {
            caminhar(Grafo, proxLinha, proxColuna, percursoAtual);
          }
     }
}