Submission #1609280

---

Source Code Expand

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <list>
#include <string>
#include <map>
#include <numeric>
#include <queue>
#include <stack>

using namespace std;
using ll = long long;
const int dx[4] = { 1,0,-1,0 };
const int dy[4] = { 0,1,0,-1 };

int main() {

	int h, w;
	int sx, sy;
	int gx, gy;
	char c[510][510];
	queue<int> q;
	
	cin >> h >> w;

	for (int i= 0; i <= h + 1; i ++ ) {
		for (int j = 0; j <= w + 1; j++) {
			c[i][j] = '#';
		}
	}

	for (int i = 1; i <= h; i++) {
		for (int j = 1; j <= w; j++) {
			cin >> c[i][j];
			if (c[i][j] == 's') {
				sx = j; sy = i;
			}
			if (c[i][j] == 'g') {
				gx = j; gy = i;
			}
		}
	}
	q.push(sx);
	q.push(sy);

	while (!q.empty()) {
		int a = q.front(); q.pop();
		int b = q.front(); q.pop();
	//	cout << a <<' ' << b << endl;

		for (int i = 0; i < 4; i++) {
			int x = a + dx[i];
			int y = b + dy[i];

			if (x == gx && y == gy) {
				cout << "Yes" << endl;
				return 0;
			}

			if (c[y][x] == '.') {
				q.push(x);
				q.push(y);
				c[y][x] = '#';
			}

		}
	}

	cout << "No" << endl;

	return 0;
}

Submission Info

Judge Result