Submission #7447376

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
bool g[502][502],check;//小区，总体可不可行
int n,m,sx,sy,ex,ey;//行，列，开始坐标，结束坐标
int dx[]={0,0,-1,1};//偏移量
int dy[]={1,-1,0,0};

void dfs(int x,int y){
    if(check){//如果之前已经有正确情况就直接退出
        return ;
    }
    if(ex==x&&ey==y){//这是正确情况，将总体情况（check）赋值为true，之后退出
        check=true;
        return ;
    }
    /*!!!这就是为什么g要定成502x502，为的是防止越界！
    将小区外面围一圈false之后，妈妈就再也不会担心我越界了！
    毕竟是false，不会搜到，那么想要搜到再外面也不可能了。
    */
    int nowx,nowy;
    for(int i=0;i<4;i++){
        nowx=x+dx[i];nowy=y+dy[i];
        if(g[nowx][nowy]){
            g[x][y]=false;
            dfs(nowx,nowy);
            //这里不能将状态回归！
            //毕竟之前竟然到过这里那么这里的情况肯定已经全部搜我。我因为没有早些出坑，找了半天错就是不知道为啥TLE,:-(
        }
    }
}

int main(){
    //49-64行为输入
    cin>>n>>m;
    char c;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>c;
            if(c!='#'){
                g[i][j]=true;
                if(c=='s'){
                    sx=i;sy=j;
                }
                if(c=='g'){
                    ex=i;ey=j;
                }
            }
        }
    }
    g[sx][sy]=false;
    dfs(sx,sy);//搜索一下
    if(check){//Perfect ending （英）、Fin parfait（法）、Der perfekte abschluss eines（德）。中文自己查:-)
        cout<<"Yes\n";
    }
    else{
        cout<<"No\n";
    }
    return 0;
} 

Submission Info

Judge Result