Submission #2998701

---

Source Code Expand

#include<bits/stdc++.h>
#pragma warning(disable:4996)
using namespace std;
using ll = long long;
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
int main() {
	int h, w;
	cin >> h >> w;
	vector<vector<char>>field(h, vector<char>(w));
	int sx, sy, gx, gy;
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			cin >> field[i][j];
			if (field[i][j] == 's') {
				sx = i; sy = j;
				field[i][j] = '.';
			}
			else if (field[i][j] == 'g') {
				gx = i; gy = j;
				field[i][j] = '.';
			}
		}
	}
	queue<tuple<int, int, int>>que;
	set<tuple<int, int, int>>st;
	que.emplace(sx, sy, 2);
	st.emplace(sx, sy, 2);
	bool ans = false;
	while (!que.empty()) {
		int tx = get<0>(que.front());
		int ty = get<1>(que.front());
		int r = get<2>(que.front());
		que.pop();
		if (tx == gx && ty == gy) {
			ans = true;
			break;
		}
		for (int i = 0; i < 4; i++) {
			int nx = tx + dx[i];
			int ny = ty + dy[i];
			if (!(0 <= nx&&nx < h && 0 <= ny&&ny < w)) {
				continue;
			}
			if (field[nx][ny] == '#') {
				if (r == 0) {
					continue;
				}
				if (st.count(tuple<int, int, int>(nx, ny, r - 1))) {
					continue;
				}
				else {
					que.emplace(nx, ny, r - 1);
					st.emplace(nx, ny, r - 1);
				}
			}
			else {
				if (st.count(tuple<int, int, int>(nx, ny, r))) {
					continue;
				}
				else {
					que.emplace(nx, ny, r );
					st.emplace(nx, ny, r);
				}
			}
		}
	}
	cout << (ans ? "YES" : "NO") << endl;
}

Submission Info

Judge Result