Submission #3733116

---

Source Code Expand

#include<iostream>
using namespace std;
const int dx[4]={1,0,-1,0},dy[4]={0,-1,0,1};    //方向数组，和DFS一样
int a[250001],b[250001],x,y,sx,sy,ex,ey,n,m,map[501][501];
char s[501][501];
bool check=false;    //是否已经搜索到终点的判断
int main()
{
    int i,j;
    cin>>n>>m;
    for(i=1;i<=n;i++)
    for(j=1;j<=m;j++)
    cin>>s[i][j];    //输入
    for(i=1;i<=n;i++)
    for(j=1;j<=m;j++)
    {
    	if(s[i][j]=='.') map[i][j]=0;
    	if(s[i][j]=='#') map[i][j]=1;
    	if(s[i][j]=='s'){sx=i; sy=j; map[i][j]=0;}
    	if(s[i][j]=='g'){ex=i; ey=j; map[i][j]=0;}
    }    //map[i][j]为1代表不可行，0代表可行，sx和sy是起点坐标，ex和ey是终点坐标
    int head=0,tail=1;
    map[sx][sy]=-1;
    a[tail]=sx;
    b[tail]=sy;    //初始化，a数组储存x坐标，b数组储存y坐标
    while(head!=tail)    //借助队列实现BFS，算法的主体
    {
        head++;    //队头指针指向待扩展节点
        for(i=0;i<4;i++)    //可向四个方向移动
        {
            x=a[head]+dx[i];
            y=b[head]+dy[i];    //搜索与此节点相连的四个点
            if(x<=n&&x>0&&y<=m&&y>0&&!map[x][y])    //边界和障碍物以及是否访问过的判断
            {
                //如果在地图内且不是障碍格且未被访问过
                tail++;    //队尾指针加1，指向新搜索到的节点
                a[tail]=x;
                b[tail]=y;    //将此节点入队
                map[x][y]=-1;    //标记为已被访问过（障碍格为1，已访问过的格为-1）
                if(x==ex&&y==ey)  //找到了终点
                {
                    cout<<"Yes"<<endl;
                    check=1;    //后面的操作无需继续进行，退出循环
                }
            }
        }
        if(check==true) break;    //退出循环
    }
    if(check==false) cout<<"No"<<endl;    //当所有可以走到的节点都被访问之后，仍找不到目标节点，输出No
    return 0;
}

Submission Info

Judge Result