C++题解|【模板】迷宫#1 搜索|模板

迷宫

题目描述鹏鹏在一个迷宫里困住了。迷宫是长方形的，有 n 行 m 列个格子。一共有 3 类格子，空地用字符’．’ 表示，墙壁用’#’表示，陷阱用’*’表示。特别地，迷宫中有两个特殊的格子：起点用’S’表示；终点用’E’表示。起点和终点都是空地。（’S’和’E’均为大写字母）鹏鹏的任务是：从起点出发，沿着某条路径，走到终点。游戏对路径的要求有三条：每次只能向相邻格子（上/下/左/右）移动一步；不能经过墙壁（即可以经过空地和陷阱）；不能走出迷宫边界。聪明的你请告诉鹏鹏，他能完成任务吗？如果能，鹏鹏能否不经过任何陷阱就完成任务呢？输入格式第一行为两个整数 n，m（2≤n,m≤7）。接下来有 n 行，每行是一个长度为 m 的字符串，依次表示迷宫的每一行格子。输出格式有一行，是一个字符串。如果鹏鹏可以不经过任何陷阱就到达终点，输出”GOOD”；否则，如果经过若干陷阱能到达终点，输出”OK”；否则，输出”BAD”。（所有字母均为大写）输入样例 1 3 4 ##.E S*.# ...* 输出样例 1GOOD 输入样例 2 3 3 ##E S*. #.. 输出样例 2OK 提示##671*5#234*样例 1 的最优路线为 1->2->3->4->5->6->7，如上图。

【C++题解|【模板】迷宫#1】模板题
C++ Code：

#include using namespace std; int n,m,sx,sy,fx,fy; char g[10][10]; int vis[10][10]; const int dx[4]={-1,1,0,0}; const int dy[4]={0,0,-1,1}; void dfs1(int x,int y) { if(x==fx and y==fy) { cout<<"GOOD"; exit(0); } else { for(int i=0; i<4; i++) { int tx=x+dx[i]; int ty=y+dy[i]; if(tx>=1 and tx<=n and ty>=1 and ty<=m and !vis[tx][ty] and (g[tx][ty]=='.' or g[tx][ty]=='E')) { vis[tx][ty]=1; dfs1(tx,ty); vis[tx][ty]=0; } } } } void dfs2(int x,int y) { if(x==fx and y==fy) { cout<<"OK"; exit(0); } else { for(int i=0; i<4; i++) { int tx=x+dx[i]; int ty=y+dy[i]; if(tx>=1 and tx<=n and ty>=1 and ty<=m and !vis[tx][ty] and g[tx][ty]!='#') { vis[tx][ty]=1; dfs2(tx,ty); vis[tx][ty]=0; } } } } int main() { cin>>n>>m; for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) { cin>>g[i][j]; if(g[i][j]=='S') sx=i,sy=j; if(g[i][j]=='E') fx=i,fy=j; } vis[sx][sy]=1; dfs1(sx,sy); memset(vis,0,sizeof(vis)); vis[sx][sy]=1; dfs2(sx,sy); cout<<"BAD"; return 0; }