Submission #11234344

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
char maze[500][500];
int a[4]={0,0,1,-1};
int vis[500][500];
int b[4]={1,-1,0,0};
int flag=0;
int bx,by,ex,ey;
int n,m;
void dfs(int x,int y){
        if(flag==1) return;
        if(maze[x][y]=='g'){
            flag=1;
            return;
        }
        if(maze[x][y]=='#'||!(x>=0&&x<n&&y>=0&&y<m))
            return;

        for(int i=0;i<4;i++){
            int tx=x+a[i];
            int ty=y+b[i];
            if(maze[tx][ty]!='#'&&tx>=0&&tx<n&&ty>=0&&ty<m&&vis[tx][ty]==0){
                //cout<<tx<<" "<<ty<<endl;
                vis[tx][ty]=1;
                dfs(x+a[i],y+b[i]);
                vis[tx][ty]=0;
            }

        }
        return;

}

int main(){

    cin>>n>>m;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++){
            cin>>maze[i][j];
            if(maze[i][j]=='s'){
                bx=i;
                by=j;
            }
            if(maze[i][j]=='g'){
                ex=i;
                ey=j;
            }
    }
    dfs(bx,by);
    if(flag==1) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

Submission Info

Judge Result