本文最后更新于 965 天前,其中的信息可能已经有所发展或是发生改变。
原题链接
描述
小明现在在玩一个游戏,游戏来到了教学关卡,迷宫是一个N*M的矩阵。
小明的起点在地图中用“S”来表示,终点用“E”来表示,障碍物用“#”来表示,空地用“.”来表示。
障碍物不能通过。小明如果现在在点(x,y)处,那么下一步只能走到相邻的四个格子中的某一个:(x+1,y),(x-1,y),(x,y+1),(x,y-1);
小明想要知道,现在他能否从起点走到终点。
输入格式:
本题包含多组数据。
每组数据先输入两个数字N,M
接下来N行,每行M个字符,表示地图的状态。
数据范围:
2<=N,M<=500
保证有一个起点S,同时保证有一个终点E.
输出格式:
每组数据输出一行,如果小明能够从起点走到终点,那么输出Yes,否则输出No
输入样例:
输出样例
分析
- 走出迷宫需要对每一个点进行搜索,考虑
DFS
和BFS
- 首先需要记录
S
的坐标
- 从
S
开始搜索,需要偏移量数组
- 对于
DFS
在搜索时,若搜到E
点则标记答案
- 对于
BFS
在搜随时,若搜到E
点直接返回
DFS代码
| #include <bits/stdc++.h> |
| using namespace std; |
| |
| const int N=510; |
| |
| int n,m; |
| |
| char mp[N][N]; |
| |
| bool vis[N][N]; |
| |
| int s1,s2; |
| |
| int dx[]={0,0,1,-1},dy[]={1,-1,0,0}; |
| |
| bool flag; |
| |
| void dfs(int x,int y){ |
| |
| if(mp[x][y]=='E'){ |
| flag=1; |
| } |
| |
| for(int i=0;i<4;i++){ |
| |
| int l=x+dx[i],r=y+dy[i]; |
| if(l>=1&&l<=n&&r>=1&&r<=m&&!vis[l][r]&&mp[l][r]!='#'){ |
| vis[l][r]=1; |
| dfs(l,r); |
| } |
| |
| } |
| |
| } |
| |
| int main(){ |
| |
| while(cin>>n>>m){ |
| |
| |
| flag=0; |
| memset(vis,0,sizeof vis); |
| memset(mp,0,sizeof mp); |
| |
| for(int i=1;i<=n;i++){ |
| for(int j=1;j<=m;j++){ |
| cin>>mp[i][j]; |
| if(mp[i][j]=='S'){ |
| s1=i; |
| s2=j; |
| } |
| } |
| } |
| |
| dfs(s1,s2); |
| |
| if(flag) cout<<"Yes"<<endl; |
| else cout<<"No"<<endl; |
| |
| } |
| |
| return 0; |
| |
| } |
BFS代码
| #include <bits/stdc++.h> |
| using namespace std; |
| |
| const int N=510; |
| |
| int n,m; |
| |
| char mp[N][N]; |
| |
| bool vis[N][N]; |
| |
| int s1,s2; |
| |
| int dx[]={0,0,1,-1},dy[]={1,-1,0,0}; |
| |
| struct point{ |
| int x,y; |
| }; |
| |
| bool bfs(){ |
| |
| queue<point> st; |
| |
| st.push({s1,s2}); |
| vis[s1][s2]=1; |
| |
| while(!st.empty()){ |
| |
| auto p=st.front(); |
| st.pop(); |
| |
| for(int i=0;i<4;i++){ |
| |
| int l=p.x+dx[i],r=p.y+dy[i]; |
| if(l>=1&&l<=n&&r>=1&&r<=m&&!vis[l][r]&&mp[l][r]!='#'){ |
| if(mp[l][r]=='E') return 1; |
| vis[l][r]=1; |
| st.push({l,r}); |
| } |
| |
| } |
| |
| } |
| |
| return 0; |
| |
| } |
| |
| int main(){ |
| |
| while(cin>>n>>m){ |
| |
| |
| memset(vis,0,sizeof vis); |
| memset(mp,0,sizeof mp); |
| |
| for(int i=1;i<=n;i++){ |
| for(int j=1;j<=m;j++){ |
| cin>>mp[i][j]; |
| if(mp[i][j]=='S'){ |
| s1=i; |
| s2=j; |
| } |
| } |
| } |
| |
| if(bfs()) cout<<"Yes"<<endl; |
| else cout<<"No"<<endl; |
| |
| } |
| |
| return 0; |
| |
| } |