时间:2021-05-20
本文实例为大家分享了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
有两种方法可以解决这个问题
第一种深度优先搜索:站在入口,考虑自己下一步可以走哪里,走到下一个位置后,再考虑下一步怎么走,一直走下去,直到没有路,然后再返回最近的一个岔路口,选其它任一条没试过的路,如果不能走,再尝试其他的路,直到这个岔路口的路全部试完,再回到上一个路口,看是否能走到出口,相当于一条路走到黑
#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;}第二种方法广度优先搜索:这一步之后,把接下来一步的所有路都列出来,在之后的所有扩展之中,在以一个为下一步,再将所有的该步可以到达的下一步,全部列举出来,再将第二步的其他选择中的每一步,都一一做扩展,每次扩展,都要检查所扩展的地方有没有到达搜索的要求。
可以定义一个队列,将扩展的点位置保存在队列,将扩展完毕的点出队
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。
声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。
本文实例讲述了基于C语言实现的迷宫算法。分享给大家供大家参考,具体如下:利用c语言实现迷宫算法,环境是vc++6.0.#include#include#incl
本文实例讲述了C语言实现简单的走迷宫游戏的方法,代码完整,便于读者理解。学数据结构时用“栈”写的一个走迷宫程序,实际上用到双向队列,方便
本文实例讲述了基于C语言实现迷宫游戏的方法,代码备有较为详尽的注释,便于读者理解。通过该游戏代码可以很好的复习C语言的递归算法与流程控制等知识,相信对于学习游戏
本文实例为大家分享了C语言实现简单的数据结构迷宫实验,供大家参考,具体内容如下分析:迷宫实验主要有两部分操作,其一是对迷宫的生成,其二是寻路使用栈的操作。步骤:
本文实例为大家分享了C++实现走迷宫小游戏的具体代码,供大家参考,具体内容如下源码下载:C++实现走迷宫小游戏主程序代码:#include#include#in