Submission #7143044

---

Source Code Expand

#include <bits/stdc++.h>
#include <algorithm>
#include <math.h>
#include <queue>
#include <cstdio>
using namespace std;

template <class T> using V = vector<T>;
template <class S, class T> using P = pair<S, T>;
template <class... T> using TP = tuple<T...>;

using ll = long long;
using db = double;
using ldb = long db;
using str = string;
using vll = V<ll>;
using vvll = V<V<ll>>;
using vvvll = V<V<V<ll>>>;
using pll = P<ll,ll>;
using tpll = TP<ll,ll,ll>;
using vpll =V<pll>;
using vvpll = V<vpll>;
using vtpll = V<tpll>;
using vst = V<str>;
using vch = V<char>;
using vvch = V<vch>;

#define FOR(i,a,b) for(ll i=(a);i<(ll)(b);i++)
#define rFOR(i,a,b) for(ll i=(b);i>(ll)(a);i--)
#define oFOR(i,a,b) for(ll i=(a);i<(ll)(b);i+=2)
#define bgn begin()
#define en end()
#define SORT(a) sort((a).bgn,(a).en)
#define REV(a) reverse((a).bgn,(a).en)
#define fi first
#define se second
#define sz size()
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) __lcm(a,b)
#define co(a) cout<<a<<endl
#define ci(a) cin>>a
#define pb(a) push_back(a)
#define pob pop_back()
#define mp make_pair
#define mt make_tuple
#define pbmp(a,b) push_back(mp(a,b))
#define subs(a,b) substr(a,b)
#define cfs(a) cout<<fixed<<setprecision(a) //
#define INF 1e16
#define mod 1e9+7
/*vvll v(n,vll(m)) n行m列
A.erase(A.begin()+i); 配列Aのi番目を消せる
std::binary_search(v.bgn,v.en,a); 二分探索
abs(a,b)   pow(a,n)  to_string  stoll
auto Iter=lower_bound(v.bgn,v.en,a); v[i]>=aのv[i]
v.insert(lower_bound(v.bgn,v.en,a),b); bを入れられる
lower upper  co(*Iter) co(Iter-v.bgn) v[i]>=aのi
priority_queue<ll> pque;  pque.push(ai);
pque.top()=max(ai)  pque.pop() pque.sz
*/

const int MAX = 510000;
const int MOD = 1000000007;
long long fac[MAX], finv[MAX], inv[MAX];
void Comuse() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
#define comuse Comuse()
ll combi(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

vvch v(500,vch(500));
vvll ve(500,vll(500));
bool D=false;
void dfs(ll sh,ll sw,ll h,ll w){
  if(D)return;
  if(ve[sh][sw]>0)return;
  ve[sh][sw]++;
  //co(sh<<sw);
  if(sh-1>=0){
    if(v[sh-1][sw]=='.')dfs(sh-1,sw,h,w);
    if(v[sh-1][sw]=='g')D=true;
  }
  if(sw-1>=0){
    if(v[sh][sw-1]=='.')dfs(sh,sw-1,h,w);
    if(v[sh][sw-1]=='g')D=true;
  }
  if(sh+1<h){
    if(v[sh+1][sw]=='.')dfs(sh+1,sw,h,w);
    if(v[sh+1][sw]=='g')D=true;
  }
  if(sw+1<w){
    if(v[sh][sw+1]=='.')dfs(sh,sw+1,h,w);
    if(v[sh][sw+1]=='g')D=true;
  }
}

int main(){
  ll h,w;
  cin>>h>>w;
  ll sh,sw;
  FOR(i,0,h){
    FOR(j,0,w){
      cin>>v[i][j];
      if(v[i][j]=='s'){
        sh=i,sw=j;
      }
    }
  }
  //co(v[0][0]);
  dfs(sh,sw,h,w);
  if(D)co("Yes");
  else co("No");
}

Submission Info

Judge Result