-1

Buenas , me encuentro ante un problema recursivo para encontrar la salida de un laberinto en una matriz bidimensional. La leyenda de este laberinto es:

'E' = entrada
'S' = salida
'#' = pared
' ' = camino

La idea es que el programa me marque un camino que vaya desde la entrada a la salida y lo marque con el caracter 'O'. El laberinto de la matriz esta perfectamente generado y coge sin problema la posicion de la entrada y la salida en el mismo Habia pensado en implementarlo utilizando el backtracking pero no consigo aplicarlo correctamente dado que no consigo hacerme a la idea de como puedo ejecutarlo para que funcione correctamente. ¿Alguna idea de como implementarlo?

Struct:

typedef struct{
  char Laberinto[FIL][COL];
}Tablero;

Subprograma recursivo para salir

void salir (int x,int y,int *resultado_x,int *resultado_y , Tablero *tab) 
{
  x = entrx; //Coordenada x de la entrada
  y = entry; //Coordenada y de la entrada

  if(tab->Laberinto[x][y]==' ') //camino libre { tab->Laberinto[x][y]=3;
   salir(x+1,y,resultado_x,resultado_y, &*tab);
   salir(x-1,y,resultado_x,resultado_y ,&*tab);
   salir(x,y+1,resultado_x,resultado_y ,&*tab);
   salir(x,y-1,resultado_x,resultado_y ,&*tab); }
  if(tab->Laberinto[x][y]=='#') //pared 
  { return; }
  if(tab->Laberinto[x][y]=='o') //ya estuve aqui 
  { return; }
  if(tab->Laberinto[x][y]=='S') //encontre la salida {
   *resultado_x=x;
   *resultado_y=y; return; } 
}

Subprograma que me genera el tablero y me encuentra las coordenadas de la entrada

void EncontrarEntradas(Tablero *tab) {

 int i , j , x , y;
 int entrada = 0
 int entrx = 0, entry = 0;
 int resultado_x = 0 , resultado_y = 0;

 for(i = 0; i < FIL-1; i++)
 {
   for (j = 0; j < COL; j++ )
   {
         printf("%c",tab->Laberinto[i][j]);

         if (tab->Laberinto[i][j] == 'S')
         {
             salx = j;
             saly = i;
             salida = 1;

         }
         if (tab->Laberinto[i][j] == 'E')
         {
             x = j;
             y = i;
             entrada = 1;
         }

   }
 }


 salir(x,y,&resultado_x,&resultado_y , &tab);

}
1
  • 3
    Si no consigues aplicarlo quiere decir que algo has probado... ¿Por qué no empiezas poniendo ese código? Si no publicas nada parecerá que estás pidiendo que te hagamos los deberes y no te gustará que pensemos eso.
    – eferion
    el 9 may. 2017 a las 15:19

1 respuesta 1

3

Tu algoritmo no tiene mucho sentido. Lo que estás intentando es inundar todos los posibles caminos cuando deberías quedarte con solo uno. La idea tendría que ser algo similar a:

  • si estoy en la casilla de meta, retorno 1
  • si estoy en una pared o en una casilla con 'o' o en la casilla de entrada, retorno 0
  • si estoy en la casilla de entrada:
    • si ya he pasado por la misma, retorno 0 (el camino anterior no es válido)
    • pruebo a llamar recursivamente a la función para probar arriba
    • pruebo a llamar recursivamente a la función para probar abajo
    • pruebo a llamar recursivamente a la función para probar izquierda
    • pruebo a llamar recursivamente a la función para probar derecha
    • algun camino debería ser solucion pero bueno, procesar este caso queda a tu juicio
  • si estoy en un pasillo:
    • lo marco con la 'o'
    • pruebo a llamar recursivamente a la función para probar arriba
    • pruebo a llamar recursivamente a la función para probar abajo
    • pruebo a llamar recursivamente a la función para probar izquierda
    • pruebo a llamar recursivamente a la función para probar derecha
    • si las cuatro llamadas me devuelve 0 esta casilla no esta en el camino de salida, sustituyo el 'o' por ' ' y retorno 0
    • si cualquiera de las 4 llamadas anteriores me devuelve 1 es que he encontrado la salida, retorno 1

Además, no veo razón para que la función recursiva devuelva unas coordenadas. ¿Coordenadas a dónde? ¿A la salida? ¿A cada iteración? ¿?

Es decir, para permitir deshacer las rutas incorrectas, la función debería tener una firma tal que:

    int salir(int x,int y,Tablero *tab) 
 // ^^^
 // Importante!!!

¿Y cómo implementarla? Siguiendo los pasos anteriores es sencilla

int salir (int x,int y,Tablero *tab,int primero)
{
  char* c = &tab->Laberinto[x][y];

  if( *c == 'S' )
    return 1;
  else if( *c == 'E' )
  {
    if( primero )
      if( salir(x+1,y,tab,0) || salir(x-1,y,tab,0) || salir(x,y+1,tab,0) || salir(x,y-1,tab,0) )
        return 1;
  }
  else if( *c == ' ' )
  {
    *c = 'o';
    if( salir(x+1,y,tab,0) || salir(x-1,y,tab,0) || salir(x,y+1,tab,0) || salir(x,y-1,tab,0) )
      return 1;
    else
    {
      if( *c == 'o' )
        *c = ' ';
    }
  }

  return 0;
}

El nuevo argumento que ha aparecido en la función sirve para impedir que el algoritmo pueda saltar por la 'E' un número indefinido de veces. Solo se va a permitir que la primera llamada este posicionada sobre esta letra.

Adicionalmente tu función para encontrar el punto de entrada al laberinto tiene errores:

void EncontrarEntradas(Tablero *tab) {

  int i , j , x , y;
  int entrada = 0
  int entrx = 0, entry = 0;
  int resultado_x = 0 , resultado_y = 0;

  for(i = 0; i < FIL-1; i++) // <<--- ¿Por que no verificas la ultima fila?
  {
    for (j = 0; j < COL; j++ )
    {
      if (tab->Laberinto[i][j] == 'E')
      {
        x = j; // <<--- esta deberia ser i
        y = i; // <<--- esta deberia ser j
        entrada = 1;
      }
    }
  }

  salir(x,y,&tab,1); // Asi se deberia llamar ahora a la funcion recursiva
}

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.