Submission #420576

---

Source Code Expand

#include <vector>
#include <stack>
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <queue>
#include <unordered_map>
#include <functional>
#include <limits>

#include <cmath>
#include <cstdio>

using namespace std;

vector<int> par;
void init(int n){
	par.resize(n);
	for(int x=0;x<n;++x){par[x]=x;}
}
//find root
int find(int x){
	if(par[x]==x){ return x; }
	else{ return par[x]=find(par[x]); }
}
//same root?
bool same(int x,int y){
	return find(x)==find(y);
}
//union!
void unions(int x,int y){
	x=find(x); y=find(y);
	if(x==y){ return; }
	par[x]=y;
}

vector<int> furui;
vector<int> furui_list;

void furui_init(int N){
	furui.assign(N+1,0);
	furui[0]=0; furui[1]=1;
	furui_list.reserve(500);
	for(int i=2;i<=N;++i){
		furui[i]=i;
		int limit=sqrt(i)+1;
		bool is_p=true;
		for(auto p:furui_list){
			is_p = i%p!=0;
			if(!is_p){ furui[i]=i/p; break;}
			if( p>limit+1 ){ break; }
		}
		if(is_p){ furui_list.push_back(i); }
	}
}

struct LoadTo{
	long to;
	long cost;
	LoadTo(long _to=-1,long _cost=-1):to(_to),cost(_cost){}
	bool operator <(const LoadTo &rhs){
		return cost < rhs.cost;
	}
};
vector<list<LoadTo>> lds;
vector<long> dtbl;
void dijk_init_tbl(long num){
	dtbl.assign(num,numeric_limits<long>::max());
}
void dijk_init(long num){
	dijk_init_tbl(num);
	lds.assign(num,list<LoadTo>());
}
void dijk_add(long from,long to,long cost){
	lds[from].emplace_back(to,cost);
	lds[to].emplace_back(from,cost);
}
void dijk_calc(long start){
	typedef pair<long,long> P;
	priority_queue< P,vector<P>,greater<P> > q; //コスト、町
	q.emplace(0, start);
	dtbl[start] = 0;

	while(!q.empty()){
		auto ex = q.top(); q.pop();
		auto n = ex.second;
		if(ex.first > dtbl[n]){continue;}
		for( auto it : lds[n] ){
			if(dtbl[n]+it.cost < dtbl[it.to] ){
				dtbl[it.to] = dtbl[n]+it.cost;
				q.emplace( dtbl[it.to], it.to );
			}
		}
	}
}

vector<vector<long>> wfdtbl;
const long wf_inf(){ return numeric_limits<long>::max()/2; }
void wf_init(long N){
	wfdtbl.assign(N, vector<long>(N,wf_inf()) );
	for(int i=0;i<N;++i){ wfdtbl[i][i]=0; }
}
void wf_add(long from,long to,long cost){
	wfdtbl[from][to] = cost;
}
bool wf_shortest(long from,long to,long cost){return wfdtbl[from][to] > cost;}
void wf_calc_only(long v1,long v2){
	const int N=wfdtbl.size();
	for(int i=0;i<N;++i){
		for(int j=0;j<N;++j){
			if( wfdtbl[i][j] - wfdtbl[i][v1] > wfdtbl[v1][v2]+wfdtbl[v2][j] ){ 
				wfdtbl[i][j]=wfdtbl[i][v1]+wfdtbl[v1][v2]+wfdtbl[v2][j];
			}
			if( wfdtbl[i][j] - wfdtbl[i][v2] > wfdtbl[v2][v1]+wfdtbl[v1][j] ){
				wfdtbl[i][j]=wfdtbl[i][v2]+wfdtbl[v2][v1]+wfdtbl[v1][j];
			}
		}
	}
}

void wf_calc(){
	const int N = wfdtbl.size();
	for(int k=0;k<N;++k){
		for(int i=0;i<N;++i){
			for(int j=0;j<N;++j){
				if(wfdtbl[i][k]<wfdtbl[i][j]-wfdtbl[k][j]){
					wfdtbl[i][j] = wfdtbl[i][k] + wfdtbl[k][j];
				}
			}
		}
	}
}

int main(int argc,char **argv){
	int H,W;
	cin >> H >> W;
	vector< vector<char> > cells(H,vector<char>(W,'X'));
	struct Pos{
		int x,y;
		Pos(int _x,int _y):x(_x),y(_y){}
		Pos operator+(const Pos &lt){ return Pos(x+lt.x,y+lt.y); }
	};
	queue<Pos> work;

	for(int y=0;y<H;++y){
		for(int x=0;x<W;++x){
			cin >> cells[y][x];
			if( cells[y][x]=='s'){
				work.push(Pos(x,y));
				cells[y][x]='F';
			}
		}
	}

	Pos d[4]={Pos(1,0),Pos(0,1),Pos(-1,0),Pos(0,-1)};
	while(work.size()>0){
		Pos np = work.front();
		work.pop();
		for(int i=0;i<sizeof(d)/sizeof(Pos);++i){
			Pos xp = np + d[i];
			if(xp.x<0||xp.y<0||xp.x>=W||xp.y>=H){ continue; }
			char c = cells[xp.y][xp.x];
			if(c=='#' || c=='F'){ continue; }
			if(c=='g'){ cout<<"Yes"<<endl; return 0; }
			work.push(xp);
			cells[xp.y][xp.x] = 'F';
		}
	}
	cout<<"No"<<endl;

	return 0;
}

Submission Info

Judge Result