C语言实现走迷宫

时间:2022-07-02 06:38:25

本文实例为大家分享了C语言实现走迷宫的具体代码,供大家参考,具体内容如下

描述

给一张个迷宫,问能否从起点走到终点,只能往上下左右走,不能斜着走

输入

多组测试数据,每组第一行两个正整数,分别为n和m

表示n这个迷宫有n行m列(0<n,m<10)

接着是n行m列,

'#'表示路

‘*'表示墙

‘S'表示起点

‘T'表示终点

输出

每组测试数据输出一个结果,如果能从S走到T,输出“YES”,否则输出“NO”

输入样例:

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

输出样例:

YES
NO

有两种方法可以解决这个问题

第一种深度优先搜索:站在入口,考虑自己下一步可以走哪里,走到下一个位置后,再考虑下一步怎么走,一直走下去,直到没有路,然后再返回最近的一个岔路口,选其它任一条没试过的路,如果不能走,再尝试其他的路,直到这个岔路口的路全部试完,再回到上一个路口,看是否能走到出口,相当于一条路走到黑

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<bits/stdc++.h>
 
using namespace std;
char a[20][20];  //存储迷宫字符数组
int flag,m,n;
int sdep_x[4]={-1,1,0,0},sdep_y[4]={0,0,-1,1};//控制上下左右方向
int vis[20][20]; //标记走过的路
void dfs(int x,int y)
{
 vis[x][y]=1; //代表被标记过了
 if(a[x][y]=='T') //找到出口
 {
  flag=1;
  return;
 }
  for(int i=0;i<4;i++) //搜索路径
  {
   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)//搜索路径的条件
   {
    dfs(h,l);
   }
  }
}
 
int main()
{
 while(cin>>n>>m)
 {
  memset(vis,0,sizeof(vis));//初始化数组
  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')//先找到路口
    {
     f=i;
     g=j;
    }
   }
  dfs(f,g);
  if(flag)
   cout<<"YES"<<endl;
  else
   cout<<"NO"<<endl;
 }
 return 0;
}

第二种方法广度优先搜索:这一步之后,把接下来一步的所有路都列出来,在之后的所有扩展之中,在以一个为下一步,再将所有的该步可以到达的下一步,全部列举出来,再将第二步的其他选择中的每一步,都一一做扩展,每次扩展,都要检查所扩展的地方有没有到达搜索的要求。
可以定义一个队列,将扩展的点位置保存在队列,将扩展完毕的点出队

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#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//定义一个结构体,里面包含x,y成员                                                        
{
 int x;
 int y;
};
data s,p;//定义两个结构体变量
queue<data>q;//定义一个队列q
int BFS()
{
 while(!q.empty())//当队列不为空时
 {
  p=q.front();//返回队列的第一个元素
  vis[p.x][p.y]=1;
  q.pop();//删除队列中最靠前的元素
  if(a[p.x][p.y]=='T')//如果找到出口
   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]!='*')//搜索条件
     q.push(s);//将扩展的点的位置存入队尾
   }
  }
 }
 return 0;
}
int main()
{
 while(cin>>n>>m)
 {
  while(!q.empty())
  {
   q.pop();//清空队列中的元素
  }
  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);//将路口的位置保存在队尾
    }
   }
   }
   if(BFS())
   cout<<"YES"<<endl;
   else
   cout<<"NO"<<endl;
 
 }
 return 0;
}

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持服务器之家。

原文链接:https://blog.csdn.net/weixin_45768308/article/details/107447338