An implementation method for solving maze problems in C language data structures

An implementation method for solving maze problems in C language data structures

In this section of learning data structure stack, I encountered the problem of finding a maze

First of all, the "exhaustive solution" is usually used to solve the maze problem, that is, starting from the entrance and testing in a certain direction. If you can get through, you can continue to go forward. Otherwise, you can return to the original way and continue to test in another direction until you get out.

We can start by building an 8 by 8 maze where the outermost one is the wall

int mg[M+2][N+2]={
 {1,1,1,1,1,1,1,1,1,1},
 {1,0,0,1,0,0,0,1,0,1},
 {1,0,0,1,0,0,0,1,0,1},
 {1,0,0,0,0,1,1,0,0,1},
 {1,0,1,1,1,0,0,0,0,1},
 {1,0,0,0,1,0,0,0,0,1},
 {1,0,1,0,0,0,1,0,0,1},
 {1,0,1,1,1,0,1,1,0,1},
 {1,1,0,0,0,0,0,0,0,1},
 {1,1,1,1,1,1,1,1,1,1},
}

As shown above, 0 corresponds to the channel square and 1 to the wall. For each square in the maze, there are four squares adjacent to each other. We stipulate that the position of the square in the i row and the j column is (i,j). The top of (i,j) is (i-1,j), the bottom is (i+1,j), the left is (i, j-1), and the right is (i,j+1).

struct {
  int i;// Current bearing line 
  int j;// Current bearing column 
  int di;// Under the 1 One can go the azimuth number 
}St[MaxSize];// The stack 
int top=-1;// Initializes the top pointer on the stack 

Let's look at the text process

First, push the entry into the stack (the initial position is -1), and loop if the stack is not empty: take the top box (do not push the stack), if the box is the exit, push the stack. If such a square exists, its orientation is saved to the top element of the stack and the walkable adjacent square is pushed onto the stack.

Corresponding algorithm:

void mgpath(int x1,int y1,int x2,int y2){
  int i.j,di,find,k;
  top++;
  St[top].i=x1; St[top].j=y1; St[top].di=-1; mg[x1][y1]=-1;

 while (top>-1){
  i=St[top].i; j=St[top].j; di=St[top].di;
  if (i==x2 && j==y2){
     printf(" The maze path is as follows: \n");
    for (k=0;k<=top;k++){
      printf("\t(%d,%d)",St[k].i,S[k].j);
       if ((k+1)%5==0) printf("\n"); // The output 5 A change 1 line 
       }
  printf("\n");  // find 1 End after path 
  return ;
  }
  find=0;
  while (di<4 && find==0){
  di++;
  switch(di){
   case 0: i=St[top].i-1; j=S[top].j;break;
   case 1: i=St[top].i;  j=St[top].j+1;break;
   case 2: i=St[top].i+1;j=St[top].j;break;
   case 3: i=St[top].i;  j=St[top].j-1;break;
   }
    if(mg[i] [j]==0) find=1;
  }
  if (find==1){  // Found under the 1 One square can be walked 
   St[top].di=di;// Modify the value at the top of the stack 
   top++;  // Under the 1 One walkable block to the stack 
  St [top].i=i; St[top].j=j;St[top].di=-1;
  mg[i] [j]=-1;// Avoid repeating to the square 
 }
  else{  // There is no path , Do the unstack operation 
    mg[St[top].i] [St[top].j]=0;// Make the location a walkable square for the other path 
    top--;
    }

}
  printf(" There is no path !\n");
}

Of course, we can also use the queue to find the optimal algorithm for the maze. This is just one example to understand the stack

Thank you for reading, I hope to help you, thank you for your support of this site!