这篇文章主要为大家详细介绍了C语言实现走迷宫，文中示例代码介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们可以参考一下
本文实例为大家分享了C语言实现走迷宫的具体代码，供大家参考，具体内容如下
描述
给一张个迷宫，问能否从起点走到终点，只能往上下左右走，不能斜着走
输入
多组测试数据，每组第一行两个正整数，分别为n和m
表示n这个迷宫有n行m列(0<n,m<10)
接着是n行m列，
‘#’表示路
‘*’表示墙
‘S’表示起点
‘T’表示终点
输出
每组测试数据输出一个结果，如果能从S走到T，输出“YES”,否来源gaodaimacom搞#代%码网则输出“NO”
输入样例：
2 2
S*
#T
3 3
S*#
#T
##
输出样例：
YES
NO
有两种方法可以解决这个问题
第一种深度优先搜索：站在入口，考虑自己下一步可以走哪里，走到下一个位置后，再考虑下一步怎么走，一直走下去，直到没有路，然后再返回最近的一个岔路口，选其它任一条没试过的路，如果不能走，再尝试其他的路，直到这个岔路口的路全部试完，再回到上一个路口，看是否能走到出口，相当于一条路走到黑
#include 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=0&&h=0&&l>n>>m) { memset(vis,0,sizeof(vis));//初始化数组 flag=0; int f,g; for(int i=0;i<n;i++) for(int j=0;j>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; }
第二种方法广度优先搜索：这一步之后，把接下来一步的所有路都列出来，在之后的所有扩展之中，在以一个为下一步，再将所有的该步可以到达的下一步，全部列举出来，再将第二步的其他选择中的每一步，都一一做扩展，每次扩展，都要检查所扩展的地方有没有到达搜索的要求。
可以定义一个队列，将扩展的点位置保存在队列，将扩展完毕的点出队
#include 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;//定义两个结构体变量 queueq;//定义一个队列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=0&&s.x=0&&s.y>n>>m) { while(!q.empty()) { q.pop();//清空队列中的元素 } for(int i=0;i<n;i++) for(int j=0;j>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; }
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持gaodaima搞代码网。
以上就是C语言实现走迷宫的详细内容，更多请关注gaodaima搞代码网其它相关文章！
搞代码网（gaodaima.com）提供的所有资源部分来自互联网，如果有侵犯您的版权或其他权益，请说明详细缘由并提供版权或权益证明然后发送到邮箱[email protected]，我们会在看到邮件的第一时间内为您处理，或直接联系QQ：872152909。本网站采用BY-NC-SA协议进行授权
转载请注明原文链接：C语言实现走迷宫
转载请注明原文链接：C语言实现走迷宫
