Submission #7568992

---

Source Code Expand

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

typedef pair<int, int> P;
P s, g;
int n, m;
bool flag[505][505];
int mx[4] = {-1, 0, 1, 0};
int my[4] = {0, -1, 0, 1};

bool bfs() {
  queue<P> que;
  que.push(s);
  flag[s.first][s.second] = false;
  while (!que.empty()) {
    queue<P> pre;
    swap(que, pre);
    
    while (!pre.empty()) {
      P cur = pre.front();
      pre.pop();
      if (cur == g) return true;
      int x, y;
      x = cur.first; y = cur.second;
      flag[x][y] = false;
      rep(i, 4) {
        int tx = x+mx[i], ty = y+my[i];
        if (flag[tx][ty]) {
          flag[tx][ty] = false;
          que.push(P (tx,ty));
        }
      }
    }
  }
  return false;
}


int main() {
  cin >> n >> m;
  rep(i, n) {
    rep(j, m) {
      char c;
      cin >> c;
      if (c == '#') continue;
      flag[i+1][j+1] = true;
      if (c == 's') {
        s.first = i+1; s.second = j+1;
      }
      else if (c == 'g') {
        g.first = i+1; g.second = j+1;
      }
    }
  }
  cout << (bfs() ? "Yes" : "No") << endl;
  return 0;
}

Submission Info

Judge Result