Submission #765311

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define forr(x,arr) for(auto&& x:arr)
#define rep(i,a,b) for (int i = (a); i < (b); i++)
#define rrep(i,a,b) for (int i = (b)-1; i >= (a); i--)
#define ALL(x) (x).begin(), (x).end()
#define BIT(n) (1LL<<(n))
#define SZ(x) ((int)(x).size())
#define Y first
#define X second
#define DUMP( x ) cerr << #x << " = " << ( x ) << endl
typedef long long ll;
// -------------------------------------

template<typename T> inline bool inside(T y, T x, T h, T w) { return 0 <= y && y < h && 0 <= x && x < w; };

typedef pair<int, int> II;

void Main() {
  int H, W;
  cin >> H >> W;
  vector<string> M(H);
  II S, G;
  rep(y, 0, H) {
    cin >> M[y];
    rep(x, 0, W) {
      if (M[y][x] == 's') S = {y, x};
      if (M[y][x] == 'g') G = {y, x};
    }
  }

  vector<vector<bool>> used(H, vector<bool>(W, 0));
  int DY[4] = {1, 0, -1, 0};
  int DX[4] = {0, 1, 0, -1};

  stack<II> st;
  st.push(S);

  while(!st.empty()) {
    II cur = st.top(); st.pop();
    if (cur == G) {
      puts("Yes");
      return;
    }
    used[cur.Y][cur.X] = true;
    rep(i, 0, 4) {
      int ny = cur.Y + DY[i];
      int nx = cur.X + DX[i];
      if (!inside(ny, nx, H, W)) continue;
      if (M[ny][nx] == '#') continue;
      if (used[ny][nx]) continue;
      st.push({ny, nx});
    }
  }
  puts("No");
}
int main() { cin.tie(0); ios::sync_with_stdio(false); Main(); return 0; }

Submission Info

Judge Result