Submission #7067003

---

Source Code Expand

#include <bits/stdc++.h>
#define ll long long
#define rep(i,n) for(ll (i)=0;(i)<(n);++(i))
using namespace std;

int main(){
  ll h,w;
  cin>>h>>w;
  bool map[w][h];
  ll sx,sy,gx,gy;
  rep(i,h){
    rep(j,w){
      char c;
      cin>>c;
      if(c=='.'){
        map[j][i]=true;
      }else if(c=='#'){
        map[j][i]=false;
      }else if(c=='s'){
        map[j][i]=true;
        sx=j;sy=i;
      }else if(c=='g'){
        map[j][i]=true;
        gx=j;gy=i;
      }
    }
  }
  vector<vector<bool>> used(w,vector<bool>(h,false));
  stack<pair<ll,ll>> stk;
  stk.push(make_pair(sx,sy));
  while(stk.size()){
    pair<ll,ll> p=stk.top();
    stk.pop();
    ll x=p.first;
    ll y=p.second;
    used[x][y]=true;
    if(x==gx&&y==gy){
      cout<<"Yes"<<endl;
      return 0;
    }
    if(x>0&&!used[x-1][y]&&map[x-1][y]){
      stk.push(make_pair(x-1,y));
    }
    if(x<w-1&&!used[x+1][y]&&map[x+1][y]){
      stk.push(make_pair(x+1,y));
    }
    if(y>0&&!used[x][y-1]&&map[x][y-1]){
      stk.push(make_pair(x,y-1));
    }
    if(y<h-1&&!used[x][y+1]&&map[x][y+1]){
      stk.push(make_pair(x,y+1));
    }
  }
  cout<<"No"<<endl;
}

Submission Info

Judge Result