Submission #5303620

---

Source Code Expand

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <math.h>
#include <sstream>
#include <numeric>
#include <string>

using namespace std;

int main()
{
  int H, W;
  cin >> H >> W;
  vector<string> board(H);
  for (int i = 0; i < H; ++i) {
    cin >> board[i];
  }

  queue<pair<int, int> > q;
  vector<vector<bool> > visited(H, vector<bool> (W, false));

  bool done = false;
  for (int i = 0; i < H; ++i) {
    for (int j = 0; j < W; ++j) {
      if (board[i][j] == 's') {
	visited[i][j] = true;
	q.push(make_pair(i, j));
	done = true;
	break;
      }
    }
    if (done) break;
  }


  vector<int> dx({-1, +1,  0,  0});
  vector<int> dy({ 0,  0, -1, +1});
  
  while (not q.empty()) {
    pair<int, int> p = q.front();
    q.pop();
    int x = p.first;
    int y = p.second;
    for (int i = 0; i < 4; ++i) {
      int xx = x + dx[i];
      int yy = y + dy[i];
      if (xx < 0 or xx >= H or yy < 0 or yy >= W or board[xx][yy] == '#') continue;
      if (not visited[xx][yy]) {
	if (board[xx][yy] == 'g') {
	  cout << "Yes" << endl;
	  return 0;
	}
	visited[xx][yy] = true;
	q.push(make_pair(xx, yy));
      }
    }
  }
  
  cout << "No" << endl;
  
  return 0;
}

Submission Info

Judge Result