Submission #6749353

---

Source Code Expand

#include<iostream>
using namespace std;
const int dx[4]={1,0,-1,0},dy[4]={0,-1,0,1};
int a[250001],b[250001],x,y,sx,sy,ex,ey,n,m,map[501][501],i,j;
char s[501][501];
bool check=false;
int main(){
    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;
			}
 	   }
	}
    int head=0,tail=1;
    map[sx][sy]=-1;
    a[tail]=sx;
    b[tail]=sy;
    while(head!=tail){
        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++;
                a[tail]=x;
                b[tail]=y;
                map[x][y]=-1;
                if(x==ex&&y==ey){
                    cout<<"Yes"<<endl;
                    check=true;
                }
            }
        }
        if(check==true){
        	break;
		}
    }
    if(check==false){
    	cout<<"No"<<endl;
	}
    return 0;
}

Submission Info

Judge Result