Submission #2123267

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> P;
const LL mod=1e9+7;
const LL LINF=1LL<<62;

using state=struct{P p;int num;};
int dy[4]={0,1,0,-1};
int dx[4]={1,0,-1,0};
 
int main(){
    int H,W;
    cin >> H >> W;
    int sy=1,sx=1;
    int gy=H,gx=W;
    queue<state> qu;
    char s[H][W];
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            cin >> s[i][j];
            if(s[i][j]=='s'){
                sx=j,sy=i;
            }
            if(s[i][j]=='g'){
                gx=j,gy=i;
            }
        }
    }
    qu.push({make_pair(sx,sy),0});
    while(qu.size()){
        state y;
        y = qu.front();
        qu.pop();
        P e;
        e=y.p;
        if(e.first==gx&&e.second==gy){
            puts("Yes");
            return 0;
        }
        s[e.second][e.first]='#';
        for(int i=0;i<4;i++){
            int nx,ny;
            nx=e.first+dx[i];
            ny=e.second+dy[i];
            if(0<=nx&&nx<W&&0<=ny&&ny<H&&s[ny][nx]!='#'){
                qu.push({make_pair(nx,ny),y.num+1});
                s[ny][nx]='#';
            }
        }
    }
    puts("No");
    return 0;
}

Submission Info

Judge Result