Submission #7578591

---

Source Code Expand

#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define MOD 1000000007
#define INF (1<<30)
#define LINF (1LL<<60)
#define endl "\n"
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define reprev(i,n) for(int (i)=(n-1);(i)>=0;(i)--)
#define Flag(x) (1<<(x))
#define Flagcount(x) __builtin_popcount(x)
#define pint pair<int,int>
#define pdouble pair<double,double>
typedef unsigned long long int ull;
typedef long long lint;

char c[500][500];
bool reach[500][500]={};
int H,W;

void DFS(int x,int y){
  if(x<0 || x>=H || y<0 || y>=W || c[x][y]=='#') return;
  if(reach[x][y]==1) return;
  reach[x][y]=1;
  DFS(x,y+1);
  DFS(x,y-1);
  DFS(x+1,y);
  DFS(x-1,y);
  return;
}
 
int main(void){
  cin >> H >> W;
  rep(i,H) rep(j,W) cin >> c[i][j];
  int sx,sy,gx,gy;
  rep(i,H){
    rep(j,W){
      if(c[i][j]=='s') sx=i,sy=j;
      if(c[i][j]=='g') gx=i,gy=j;
    }
  }
  DFS(sx,sy);
  if(reach[gx][gy]==1) cout << "Yes" << endl;
  else cout << "No" << endl;
}

Submission Info

Judge Result