Labyrinth recursive algorithm

Question

Labyrinth recursive algorithm

Navigation

#1 by (2 votes)

-1

Good, I am faced with a recursive problem to find the exit of a labyrinth in a bidimensional matrix. The legend of this labyrinth is:

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

The idea is that the program marks a path that goes from the entrance to the exit and marks it with the character 'O'. The labyrinth of the matrix is perfectly generated and takes without problem the position of the entrance and the exit in the same I had thought about implementing it using backtracking but I can not apply it correctly because I can not figure out how I can execute it to work correctly. Any idea how to implement it?

Struct:

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

Recursive subprogram to exit

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; } 
}

Subprogram that the board generates me and finds me the coordinates of the entry

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);

}

c

asked by Josemanuu 09.05.2017 в 17:17

source

1 answer

vee validate does not work Is it advisable to use two constructors in Java?

score 2 · Accepted Answer

Your algorithm does not make much sense. What you are trying to do is flood all possible paths when you should stay with only one. The idea should be something similar to:

if I'm in the goal box, return 1
if I'm on a wall or in a box with 'o' or in the input box, return 0
if I'm in the input box:
- if I've already gone through it, return 0 (the previous path is not valid)
- I try to recursively call the function to try up
- I try to recursively call the function to test below
- I try to recursively call the function to test left
- I try to recursively call the function to test right
- some way should be a solution but good, to process this case is at your discretion
If I'm in a hallway:
- I frame it with the 'o'
- I try to recursively call the function to try up
- I try to recursively call the function to test below
- I try to recursively call the function to test left
- I try to recursively call the function to test right
- if the four calls return 0 this box is not in the way out, I replace the 'o' with ' ' and return 0
- if any of the 4 previous calls returns 1 is that I found the output, return 1

Also, I see no reason for the recursive function to return coordinates. Coordinates to where? At the exit? To each iteration? ?

That is, to allow undoing incorrect routes, the function should have a signature such that:

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

And how to implement it? Following the steps above is simple

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;
}

The new argument that has appeared in the function serves to prevent the algorithm from jumping over the 'E' indefinitely. Only the first call will be allowed to be positioned on this letter.

Additionally your function to find the entry point to the labyrinth has errors:

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
}