Submission #5422227

---

Source Code Expand

// #pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
using namespace std;
#define EPS 1e-7
#define MOD 1000000007
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);
#define VI vector<int>
#define VD vector<double>
#define VC vector<char>
#define VS vector<string>
#define VVI vector<VI>
#define VVD vector<VD>
#define VVC vector<VC>
#define VVS vector<VS>
#define PII pair<int,int>
#define PIII pair<int,PII>
#define VPII vector<PII>
#define VPIII vector<PIII>
#define emb emplace_back
#define pub push_back
#define pob pop_back
#define mp make_pair
#define mp3(a,b,c) mp(a,mp(b,c))
#define fi first
#define se second
#define fir fi
#define sec se.fi
#define thr se.se
#define fou(i,a,n) for(int i=a;i<n;i++)
#define fod(i,a,n) for(int i=n-1;i>=a;i--)
#define rep(n) fou(_,0,n)
#define tra(a,x) for(auto& a : x)
#define elif(c) else if(c)
#define si(vec) ((int)(vec).size())
#define all(vec) vec.begin(),vec.end()
#define lla(vec) vec.rbegin(),vec.rend()
#define range(vec,x,y) vec.begin()+x,vec.begin()+y
#define sortup(vec) sort(all(vec))
#define sortdown(vec) sort(lla(vec))
#define eraseif(vec,condition_VAR) vec.erase(remove_if(all(vec),[&](auto VAR){return condition_VAR;}),vec.end())
#define erase_unique(vec) vec.erase(unique(all(vec)),vec.end())
#define rotateleft(vec,n) rotate(vec.begin(),vec.begin()+n,vec.end())
#define rotateright(vec,n) rotate(vec.rbegin(),vec.rbegin()+n,vec.rend())
template<class C>int minelement(vector<C>&vec){int s=si(vec);C m=0;fou(i,1,s)if(vec[i]<vec[m])m=i;return m;}
template<class C>int maxelement(vector<C>&vec){int s=si(vec);C m=0;fou(i,1,s)if(vec[i]>vec[m])m=i;return m;}
template<class C>void mini(C&a,const C&b){a=min(a,b);}
template<class C>void maxi(C&a,const C&b){a=max(a,b);}
// make_pair,vector calculate
#define opall(calc) calc(+)calc(-)calc(*)calc(/)calc(%)calc(<<)calc(>>)calc(&)calc(|)calc(^)
#define paircalc(op) template<class C1,class C2,class C3>pair<C1,C2>operator op(const pair<C1,C2>&l,const C3&r){return mp(l.first op r,l.second op r);}
#define pair2calc(op) template<class C1,class C2>pair<C1,C2>operator op(const pair<C1,C2>&l,const pair<C1,C2>&r){return mp(l.first op r.first,l.second op r.second);}
#define vectorcalc(op) template<class C1,class C2>vector<C1>operator op(const vector<C1>&l,const C2&r){int s=si(l);vector<C1> v(s);fou(i,0,s)v[i]=l[i] op r;return v;}
#define vector2calc(op) template<class C>vector<C>operator op(const vector<C>&l,const vector<C>&r){int s=min(si(l),si(r));vector<C>v(s);fou(i,0,s)v[i]=l[i] op r[i];return v;}
#define opeq(op) template<class C1,class C2>C1 operator op ## =(C1&l,const C2&r){return l=l op r;}
opall(paircalc)opall(pair2calc)opall(vectorcalc)opall(vector2calc)opall(opeq)
// iostream
#define in(T,...) T __VA_ARGS__;_cin(__VA_ARGS__)
#define out(...) _cout(__VA_ARGS__)
void _cin(){}template<class Head,class...Tail>void _cin(Head&head,Tail&&...tail){cin>>head;_cin(forward<Tail>(tail)...);}
template<class Head>void _cout(const Head&head){cout<<head<<endl;}template<class Head,class...Tail>void _cout(const Head&head,Tail...tail){cout<<head<<" ";_cout(forward<Tail>(tail)...);}
template<class C1,class C2>istream&operator>>(istream&is,pair<C1,C2>&p){return is>>p.fi>>p.se;}
template<class C>istream&operator>>(istream&is,vector<C>&vec){tra(v,vec)is>>v;return is;}
template<class C1,class C2>ostream&operator<<(ostream&os,const pair<C1,C2>&p){os<<p.fi<<" "<<p.se;return os;}
template<class C>ostream&operator<<(ostream&os,const vector<C>&vec){int vecsize=si(vec);fou(i,0,vecsize-1)os<<vec[i]<<" ";os<<vec[vecsize-1];return os;}
// math
int gcd_sub(const int&a,const int&b){if(b)return gcd_sub(b,a%b);else return a;}int gcd(const int&a,const int&b){return gcd_sub(max(a,b),min(a,b));}
int lcm(const int&a,const int&b){return a/gcd(a,b)*b;}
int fact(const int&n){return n==0?1:n*fact(n-1);}
PII comb_sub(const int&m,const int&n){return n==0?mp(1,1):mp(m,n)*comb_sub(m-1,n-1);}int comb(const int&m,const int&n){PII p=comb_sub(m,min(n,m-n));return p.fi/p.se;}
// algorithm
template<class C>vector<C>cumsum(vector<C>vec){int s=si(vec);fou(i,1,s)vec[i]+=vec[i-1];return vec;}
template<class C>vector<vector<C>>cumsum2(vector<vector<C>>vec){int s=si(vec);fou(i,1,s)vec[i]+=vec[i-1];fou(i,0,s)vec[i]=cumsum(vec[i]);return vec;}
template<class C>int binarysearch(const vector<C>vec,const C&n,const char&c){
  int left=-1;int right=si(vec);bool outleft=(c=='d'||c=='U');int getmin=(c=='u'||c=='d')?1:-1;
  while(right-left>1){
    int mid=left+(right-left)/2;
    bool OK=vec[mid]*getmin>=n*getmin;
    if(outleft==OK) left=mid;else right=mid;
  }
  return outleft?left:right;
}



#define int int64_t
// #define double long double


// mukougurahu
// mod

signed main(){
  in(int,h,w);
  VVC c(h+2,VC(w+2));
  fou(i,0,h)fou(j,0,w) cin>>c[i+1][j+1];
  fou(i,0,h+2) {c[i][0]='#';c[i][w+1]='#';}
  fou(i,0,w+2) {c[0][i]='#';c[h+1][i]='#';}

  int sx,sy,gx,gy;
  fou(i,1,h+1){
    fou(j,1,w+1){
      if(c[i][j]=='s'){
        sx=i,sy=j;
        break;
      }
    }
  }

  int x=sx,y=sy;
  string ans;
  while(true){
    if(c[x+1][y]=='g'||c[x][y+1]=='g'||c[x-1][y]=='g'||c[x][y-1]=='g'){
      ans="Yes";
      break;
    }
    if(c[x+1][y]=='.'){x++;c[x][y]='d';}
    elif(c[x][y+1]=='.'){y++;c[x][y]='r';}
    elif(c[x-1][y]=='.'){x--;c[x][y]='u';}
    elif(c[x][y-1]=='.'){y--;c[x][y]='l';}
    else{
      if(c[x][y]=='d') {c[x][y]='#';x--;}
      elif(c[x][y]=='r') {c[x][y]='#';y--;}
      elif(c[x][y]=='u') {c[x][y]='#';x++;}
      elif(c[x][y]=='l') {c[x][y]='#';y++;}
      else {
        ans="No";
        break;
      }
    }
    // fou(i,0,h+2) out(c[i]);
    // out(x,y);
  }
  out(ans);

}

Submission Info

Judge Result