原题链接:
题目
题意分析:
这道题目是有多种解法的,这里看作是一道广度优先搜索的模板题目
做题思路:
从起点开始,分别向上、下、左、右四个方向进行搜索,如果搜索到了终点,则说明能够到达终点;否则,将该点压入队列之中,继续进行下面的搜索,并将该点标记成已访问。
代码实现
#include<bits/stdc++.h>
using namespace std;
char mp[600][600];
int vis[600][600];
int dx[4]={0,1,-1,0};
int dy[4]={1,0,0,-1};
queue<int> x,y; //利用STL中的队列
void bfs(int m,int n)
{
int flag=0,i;
while(!x.empty())
{
for(i=0;i<4;i++)
{
int tx=x.front()+dx[i]; //向上下左右四个方向进行搜索
int ty=y.front()+dy[i];
if(mp[tx][ty]=='E')
{
flag=1;
cout<<"Yes"<<endl;
break;
}
if(mp[tx][ty]=='.' && tx>=0 && tx<=m-1 && ty>=0 && ty<=n-1 && !vis[tx][ty]) //如果该点是空地并且没有超过边界限制
{
x.push(tx); //将该点压入队列中
y.push(ty);
vis[tx][ty]=1; //将该点标记为已访问
}
}
if(flag==1)
{
break;
}
x.pop(); //队首的元素出队
y.pop();
}
if(flag==0)
{
cout<<"No"<<endl;
}
}
int main()
{
int m,n,i,j;
while(cin>>m>>n)
{
memset(vis,0,sizeof(vis));
memset(mp,'l',sizeof(mp)); //这里一定要将mp二维数组进行重置
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
cin>>mp[i][j];
if(mp[i][j]=='S')
{
x.push(i); //将迷宫起点的坐标位置压入队列中
y.push(j);
vis[i][j]=1; //标记起点已访问
}
}
}
bfs(m,n);
}
return 0;
}