Submission #20179519

---

Source Code Expand

#include <atcoder/all>
using namespace atcoder;
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const double pi = 3.14159265359;
const ll INF = 1LL << 60;

int h, w;
vector<string> g;
ll dist[500][500];
int sy, sx;
int gy, gx;

int main()
{
  cin >> h >> w;
  g.resize(h);
  for (string& t : g) cin >> t;
  
  for(int i = 0; i < h; i++){
    for (int j = 0; j < w; j++){
      dist[i][j] = INF;
      if (g[i][j] == 's'){
	sy = i;
	sx = j;
      }
      if (g[i][j] == 'g'){
	gy = i;
	gx = j;
      }
    }
  }

  deque<tuple<int, int, int>> q;
  q.push_front(make_tuple(sy, sx, 0));

  while (q.size() > 0){
    auto t = q.front();
    q.pop_front();
    int y = get<0>(t);
    int x = get<1>(t);
    int d = get<2>(t);
    if (d < dist[y][x]){
      dist[y][x] = d;
      vector<int> dy {-1, +1,  0,  0};
      vector<int> dx { 0,  0, -1, +1};
      for (int i = 0; i < 4; i++){
	int yy = y + dy[i];
	int xx = x + dx[i];
	if (0 <= yy && yy < h && 0 <= xx && xx < w){
	  if (g[yy][xx] != '#'){
	    q.push_front(make_tuple(yy, xx, d));
	  } if (d < 2){
	    q.push_back(make_tuple(yy, xx, d+1));
	  }
	}
      }
    }
  }

  if (dist[gy][gx] <= 2){
    cout << "YES" << endl;
  } else {
    cout << "NO" << endl;
  }
  return 0;
}

Submission Info

Judge Result