Submission #2997832

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,k,n) for(int i = (int)(k); i < (int)(n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) a.begin(), a.end()
#define MS(m,v) memset(m,v,sizeof(m))
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> pii;
const int MOD = 1e9 + 7;
template<class T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<class T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<class T>
istream& operator >> (istream& is, vector<T>& v)
{
	for (auto &i : v) is >> i;
	return is;
}
template<class T>
ostream& operator<<(ostream& os, vector<T>& v)
{
	const string delimiter = "\n";
	REP(i, v.size())
	{
		os << v[i];
		if (i != v.size() - 1) os << delimiter;
	}
	return os;
}
/*--------------------template--------------------*/

const int dx[] = { -1, 0, 1, 0 }, dy[] = { 0, -1, 0, 1 };
//const int dx[] = { -1, -1, -1, 0, 0, 1, 1, 1 }, dy[] = { 0, -1, 1, -1, 1, 0, -1, 1 };
bool valid(int x, int y, int h, int w) { return (x >= 0 && y >= 0 && x < h&&y < w); }
int place(int x, int y, int w) { return w*x + y; }

typedef tuple<int, int, int> Data;
int main()
{
	cin.sync_with_stdio(false); cout << fixed << setprecision(10);
	int h, w;
	cin >> h >> w;
	vs fld(h); cin >> fld;
	int sx, sy, gx, gy;
	REP(i, h)REP(j, w)
	{
		if (fld[i][j] == 's')
		{
			sx = i, sy = j;
			fld[i][j] = '.';
		}
		if (fld[i][j] == 'g')
		{
			gx = i, gy = j;
			fld[i][j] = '.';
		}
	}

	queue<Data> que;
	set<Data> 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;
		}
		REP(i, 4)
		{
			int nx = tx + dx[i];
			int ny = ty + dy[i];
			if (!valid(nx, ny, h, w)) continue;
			if (fld[nx][ny] == '#')
			{
				if (r == 0) continue;
				if (st.count(Data(nx, ny, r - 1))) continue;
				que.emplace(nx, ny, r - 1);
				st.emplace(nx, ny, r - 1);
			}
			else
			{
				if (st.count(Data(nx, ny, r))) continue;
				que.emplace(nx, ny, r);
				st.emplace(nx, ny, r);
			}
		}
	}
	cout << (ans ? "YES" : "NO") << endl;
	return 0;
}

Submission Info

Judge Result