Submission #6859863

---

Source Code Expand

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

typedef pair<int, int> P;
const int INF = -1;

int main(){
  int H, W, sx, sy, gx, gy;
  cin >> H >> W;
  vector<vector<char>> maze(510, vector<char>(510));
  vector<vector<bool>> d(510, vector<bool>(510, false));
  rep(i, H){
    rep(j, W){
      cin >> maze[i][j];
      if (maze[i][j] == 's'){
        sx = j;
        sy = i;
      }
      else if (maze[i][j] == 'g'){
        gx = j;
        gy = i;
      }
    }
  } 
  
  vector<int> dx = {1, 0, -1, 0};
  vector<int> dy = {0, 1, 0, -1};
  
  queue<P> que;
  que.push(P(sx, sy)); //P(sx, sy)はmake_pair(sx, sy)と同じ
  d[sy][sx] = true;
  
  while(que.size()){
    P p = que.front();
    que.pop();
    if(p.first == gx && p.second == gy) break;
    rep(i, 4){
      int nx = p.first + dx[i];
      int ny = p.second + dy[i];
      
      if(nx >= 0 && nx < W && ny >= 0 && ny < H && maze[ny][nx] != '#' && d[ny][nx] == false){
        d[ny][nx] = true;
        que.push(P(nx, ny));
      }
      
    }
    
    
  }
 
  
  if (d[gy][gx]) cout << "Yes" << endl;
  else cout << "No" << endl;
  
}

Submission Info

Judge Result