Submission #420846

---

Source Code Expand

#include <iostream>
#include <vector>
#include <cstdio>
#include <sstream>
#include <map>
#include <string>
#include <algorithm>
#include <queue>
#include <cmath>
#include <functional>
#include <set>
using namespace std;
int dx[] = {-1,0,1,0};
int dy[] = {0,1,0,-1};

int main(){
	int h,w;
	cin >> h >> w;
	vector<string> s(h);
	for(int i=0; i<h; i++){
		cin >> s[i];
	}

	int start = -1;
	int goal = -1;
	for(int i=0; i<h; i++){
		for(int j=0; j<w; j++){
			if(s[i][j] == 's') start = i*w + j;
			if(s[i][j] == 'g') goal = i*w + j;
		}
	}

	vector<bool> visit(w*h, false);
	
	function<void(int,int)> dfs = [&](int x, int y){
		//cerr << x << " " << y << endl;
		visit[y*w + x] = true;
		for(int i=0; i<4; i++){
			int xx = x + dx[i];
			int yy = y + dy[i];
			if(xx < 0 || xx >= w || yy < 0 || yy >= h) continue;
			if(s[yy][xx] == '#') continue;
			if(visit[yy*w + xx]) continue;
			dfs(xx, yy);
		}
	};

	dfs(start%w, start/w);

	cout << (visit[goal]?"Yes":"No") << endl;

	return 0;
}

Submission Info

Judge Result