Submission #420840

---

Source Code Expand

#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <deque>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <ctime>
#include <iterator>
#include <bitset>
#include <numeric>
#include <list>
#include <iomanip>
 
#if __cplusplus >= 201103L
#include <array>
#include <tuple>
#include <initializer_list>
#include <unordered_set>
#include <unordered_map>
#include <forward_list>
 
#define cauto const auto&
#endif
 
using namespace std;
 
 
typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
 
typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;
 
#define VV(T) vector<vector< T > >
 
template <class T>
void initvv(vector<vector<T> > &v, int a, int b, const T &t = T()){
v.assign(a, vector<T>(b, t));
}
 
template <class F, class T>
void convert(const F &f, T &t){
stringstream ss;
ss << f;
ss >> t;
}
 
 
#define rep(i,n) for(int i=0;i<int(n);++i)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pb push_back
 
 
#define MOD 1000000007LL
#define EPS 1e-8


int W,H;
char maze[500][500];
bool reached[500][500];

void dfs(int x, int y){
	if(x<0 || W<=x || y<0 || H<=y || maze[x][y]=='#') return;
	if(reached[x][y]) return;
	
	reached[x][y] = true;
	
	dfs(x+1, y);
	dfs(x-1, y);
	dfs(x, y+1);
	dfs(x, y-1);
}
 
int main(){
	cin>>H>>W;
	int sx,sy,gx,gy;
	rep(i,H){
		rep(j,W){
			char t;
			cin>>t;
			if(t == 's'){
				sx = i;
				sy = j;
				maze[i][j] = '.';
				continue;
			}
			if(t == 'g'){
				gx = i;
				gy = j;
				maze[i][j] = '.';
				continue;
			}
			maze[i][j] = t;
		}
	}
	rep(i,500)
		rep(j,500)
			reached[i][j] = false;
	
	dfs(sx,sy);
	
	printf("%s\n",reached[gx][gy]?"Yes":"No");
	
	return 0;
}

Submission Info

Judge Result