Submission #4045524

---

Source Code Expand

#include <bits/stdc++.h>
typedef long long ll;
#define INF 1000000000
#define MOD 1000000007
int dx[4]={1,0,-1,0},dy[4]={0,-1,0,1};
using namespace std;
int main(void){
   int h,w;
   cin>>h>>w;
   char c[h][w];
   pair<int,int>s,f;
   for(int i=0;i<h;i++){
      for(int j=0;j<w;j++){
         cin>>c[i][j];
         if(c[i][j]=='s'){
            s=make_pair(i,j);
         }
         if(c[i][j]=='g'){
            f=make_pair(i,j);
         }
      }
   }
   queue<pair<int,int>>que;
   que.push(s);
   c[s.first][s.second]='#';
   bool ok=false;
   while(!que.empty()){
      pair<int,int>now=que.front();
      que.pop();
      int nowx,nowy;
      nowy=now.first;
      nowx=now.second;
      for(int i=0;i<4;i++){
         int nexty,nextx;
         nexty=nowy+dy[i];
         nextx=nowx+dx[i];
         if(nextx>=0 and nextx<w and nexty>=0 and nexty<h and c[nexty][nextx]!='#'){
         if(c[nexty][nextx]=='g'){
         ok=true;
         break;
         }
         c[nexty][nextx]='#';
            que.push(make_pair(nexty,nextx));
         }
      }
   }
   if(ok){
      cout<<"Yes"<<endl;
   }else{
      cout<<"No"<<endl;
   }
   return 0;
}

Submission Info

Judge Result