The C language implements the maze

  • 2020-10-23 21:07:58
  • OfStack

This article is an example of C language for you to share the implementation of the maze specific code, for your reference, the specific content is as follows

describe

Give a piece of maze, ask whether you can go from the beginning to the end, can only go up and down left and right, not sideways

The input

Multiple sets of test data, two positive integers in line 1 of each set, n and m, respectively

n represents a maze with n rows m column (0 < n,m < 10)

Then n row, m column,

'#' said

The '*' said wall

'S' indicates the starting point

'T' represents the end point

The output

Each set of test data outputs 1 result. If you can go from S to T, output "YES"; otherwise, output "NO".

Input sample:

2 2
S*
#T
3 3
S*#
#T
##

Output sample:

YES
NO

There are two ways to solve this problem

1 kind of depth first search: standing at the entrance, considering their next step 1 can go where, one to the next place, and then consider the step 1, 1, go straight on, until there is no road, and then return to a fork in the road recently, choose other 1 didn't try road, if you can't walk, then try the other way, until you try all way to the fork in the road, on the back to an intersection, look to whether can go to export, the equivalent of 1 road to black


#include<bits/stdc++.h>

using namespace std;
char a[20][20];  // Stores maze character arrays 
int flag,m,n;
int sdep_x[4]={-1,1,0,0},sdep_y[4]={0,0,-1,1};// Control up, down, left and right 
int vis[20][20]; // Mark the road 
void dfs(int x,int y)
{
 vis[x][y]=1; // The symbol is marked 
 if(a[x][y]=='T') // Find the export 
 {
  flag=1;
  return;
 }
  for(int i=0;i<4;i++) // The search path 
  {
   int h=x+sdep_x[i];
   int l=y+sdep_y[i];
   if(a[h][l]!='*'&&!vis[h][l]&&h>=0&&h<n&&l>=0&&l<m)// Criteria for the search path 
   {
    dfs(h,l);
   }
  }
}

int main()
{
 while(cin>>n>>m)
 {
  memset(vis,0,sizeof(vis));// Initializing array 
  flag=0;
  int f,g;
  for(int i=0;i<n;i++)
   for(int j=0;j<m;j++) 
    cin>>a[i][j];
  for(int i=0;i<n;i++)
   for(int j=0;j<m;j++)
   {
    if(a[i][j]=='S')// Find the intersection first. 
    {
     f=i;
     g=j;
    }
   }
  dfs(f,g);
  if(flag)
   cout<<"YES"<<endl;
  else
   cout<<"NO"<<endl;
 }
 return 0;
}

Breadth first search method 2: after this step 1, the next step 1 listed all the way, after all extension, in step 1 to 1, then all of the next step 1 and step to all listed, then step 2 other choices in each step 1, 11 do extension, each extension, did all the places to check extended reach the search request.
You can define a queue, save the location of the extended point in the queue, and queue the extended point out


#include<bits/stdc++.h>
using namespace std;
int vis[20][20];
char a[20][20];
int n,m;
int step_x[4]={-1,1,0,0},step_y[4]={0,0,-1,1};
struct data// define 1 It's a structure that contains x,y Members of the                                                          
{
 int x;
 int y;
};
data s,p;// Define two structural variables 
queue<data>q;// define 1 A queue q
int BFS()
{
 while(!q.empty())// When the queue is not empty 
 {
  p=q.front();// Returns the number of rows 1 An element 
  vis[p.x][p.y]=1;
  q.pop();// Deletes the most advanced element in the queue 
  if(a[p.x][p.y]=='T')// If you find an exit, 
   return 1;
  else
  {
   for(int i=0;i<4;i++)
   {
    s.x=p.x+step_x[i];
    s.y=p.y+step_y[i];
    if(s.x>=0&&s.x<n&&s.y>=0&&s.y<m&&!vis[s.x][s.y]&&a[s.x][s.y]!='*')// The search criteria 
     q.push(s);// Stores the position of the extended points at the end of the queue 
   }
  }
 }
 return 0;
}
int main()
{
 while(cin>>n>>m)
 {
  while(!q.empty())
  {
   q.pop();// Clears the elements in the queue 
  }
  for(int i=0;i<n;i++)
   for(int j=0;j<m;j++)
   cin>>a[i][j];
   for(int i=0;i<n;i++)
   {
   for(int j=0;j<m;j++)
   {
    vis[i][j]=0;
    if(a[i][j]=='S')
    {
     s.x=i;
     s.y=j;
     q.push(s);// Save the position of the intersection at the end of the line 
    }
   }
   }
   if(BFS())
   cout<<"YES"<<endl;
   else
   cout<<"NO"<<endl;

 }
 return 0;
}

Related articles: