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