Submission #420191


Source Code Expand

#include<vector>
#include<cmath>
#include<map>
#include<cstdlib>
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#include<stack>
#include<bitset>
#include<functional>
#include<ctime>
#include<queue>
#include<deque>
#include<complex>
using namespace std;
#define pb push_back
#define pf push_front
typedef long long lint;
typedef complex<double> P;
#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
struct unionf{
	vector <int> data;
	unionf(int size):data(size,-1){}
	bool unions(int x,int y){
		x=root(x);y=root(y);
		if(x!=y){
			if(data[y]<data[x]){int d=x;x=y;y=d;}
			data[x]+=data[y];data[y]=x;
		}
		return x!=y;
	}
	bool finds(int x,int y){
		return root(x)==root(y);
	}
	int root(int x){
		return data[x]<0?x:data[x]=root(data[x]);
	}
	int find(int x){
		return -data[x];
	}
};
string ma[514];
int main()
{
	int h,w,sx,sy,gx,gy;
	int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
	cin>>h>>w;
	unionf uni(h*w+10);
	rep(i,h) cin>>ma[i];
	rep(i,h) rep(j,w){
		if(ma[i][j]=='s') sx=i,sy=j;
		if(ma[i][j]=='g') gx=i,gy=j;
		if(ma[i][j]=='#') continue;
		rep(k,4){
			int x=i+dx[k],y=j+dy[k];
			if(x<0 || y<0 || x>=h || y>=w) continue;
			if(ma[x][y]=='#') continue;
			uni.unions(i*w+j,x*w+y);
		}
	}
	if(uni.finds(sx*w+sy,gx*w+gy)) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
}

Submission Info

Submission Time
Task A - 深さ優先探索
User sky58
Language C++ (GCC 4.9.2)
Score 100
Code Size 1611 Byte
Status AC
Exec Time 64 ms
Memory 2076 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 5
AC × 83
Set Name Test Cases
Sample 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 00_sample_04.txt, 00_sample_05.txt
All 00_min_01.txt, 00_min_02.txt, 00_min_03.txt, 00_min_04.txt, 00_min_05.txt, 00_min_06.txt, 00_min_07.txt, 00_min_08.txt, 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 00_sample_04.txt, 00_sample_05.txt, 01_rnd_00.txt, 01_rnd_01.txt, 01_rnd_02.txt, 01_rnd_03.txt, 01_rnd_04.txt, 01_rnd_05.txt, 01_rnd_06.txt, 01_rnd_07.txt, 01_rnd_08.txt, 01_rnd_09.txt, 01_rnd_10.txt, 01_rnd_11.txt, 01_rnd_12.txt, 01_rnd_13.txt, 01_rnd_14.txt, 01_rnd_15.txt, 01_rnd_16.txt, 01_rnd_17.txt, 01_rnd_18.txt, 01_rnd_19.txt, 02_rndhard_00.txt, 02_rndhard_01.txt, 02_rndhard_02.txt, 02_rndhard_03.txt, 02_rndhard_04.txt, 02_rndhard_05.txt, 02_rndhard_06.txt, 02_rndhard_07.txt, 02_rndhard_08.txt, 02_rndhard_09.txt, 02_rndhard_10.txt, 02_rndhard_11.txt, 02_rndhard_12.txt, 02_rndhard_13.txt, 02_rndhard_14.txt, 02_rndhard_15.txt, 02_rndhard_16.txt, 02_rndhard_17.txt, 02_rndhard_18.txt, 02_rndhard_19.txt, 02_rndhard_20.txt, 02_rndhard_21.txt, 02_rndhard_22.txt, 02_rndhard_23.txt, 02_rndhard_24.txt, 02_rndhard_25.txt, 02_rndhard_26.txt, 02_rndhard_27.txt, 02_rndhard_28.txt, 02_rndhard_29.txt, 02_rndhard_30.txt, 02_rndhard_31.txt, 02_rndhard_32.txt, 02_rndhard_33.txt, 02_rndhard_34.txt, 02_rndhard_35.txt, 02_rndhard_36.txt, 02_rndhard_37.txt, 02_rndhard_38.txt, 02_rndhard_39.txt, 03_rndhardsmall_00.txt, 03_rndhardsmall_01.txt, 03_rndhardsmall_02.txt, 03_rndhardsmall_03.txt, 03_rndhardsmall_04.txt, 03_rndhardsmall_05.txt, 03_rndhardsmall_06.txt, 03_rndhardsmall_07.txt, 03_rndhardsmall_08.txt, 03_rndhardsmall_09.txt
Case Name Status Exec Time Memory
00_min_01.txt AC 26 ms 776 KB
00_min_02.txt AC 27 ms 732 KB
00_min_03.txt AC 25 ms 924 KB
00_min_04.txt AC 25 ms 800 KB
00_min_05.txt AC 26 ms 864 KB
00_min_06.txt AC 25 ms 736 KB
00_min_07.txt AC 24 ms 800 KB
00_min_08.txt AC 25 ms 924 KB
00_sample_01.txt AC 24 ms 932 KB
00_sample_02.txt AC 24 ms 928 KB
00_sample_03.txt AC 22 ms 920 KB
00_sample_04.txt AC 26 ms 920 KB
00_sample_05.txt AC 24 ms 928 KB
01_rnd_00.txt AC 42 ms 1956 KB
01_rnd_01.txt AC 53 ms 1956 KB
01_rnd_02.txt AC 53 ms 1952 KB
01_rnd_03.txt AC 53 ms 1952 KB
01_rnd_04.txt AC 54 ms 1960 KB
01_rnd_05.txt AC 51 ms 1952 KB
01_rnd_06.txt AC 53 ms 1960 KB
01_rnd_07.txt AC 53 ms 1948 KB
01_rnd_08.txt AC 41 ms 1952 KB
01_rnd_09.txt AC 49 ms 1952 KB
01_rnd_10.txt AC 51 ms 1952 KB
01_rnd_11.txt AC 42 ms 1964 KB
01_rnd_12.txt AC 53 ms 1956 KB
01_rnd_13.txt AC 54 ms 1952 KB
01_rnd_14.txt AC 50 ms 2076 KB
01_rnd_15.txt AC 64 ms 1952 KB
01_rnd_16.txt AC 45 ms 1948 KB
01_rnd_17.txt AC 54 ms 1960 KB
01_rnd_18.txt AC 46 ms 1952 KB
01_rnd_19.txt AC 55 ms 1960 KB
02_rndhard_00.txt AC 53 ms 1956 KB
02_rndhard_01.txt AC 55 ms 1960 KB
02_rndhard_02.txt AC 60 ms 1952 KB
02_rndhard_03.txt AC 54 ms 1960 KB
02_rndhard_04.txt AC 54 ms 1956 KB
02_rndhard_05.txt AC 54 ms 1956 KB
02_rndhard_06.txt AC 56 ms 2012 KB
02_rndhard_07.txt AC 54 ms 2028 KB
02_rndhard_08.txt AC 52 ms 1956 KB
02_rndhard_09.txt AC 53 ms 1952 KB
02_rndhard_10.txt AC 54 ms 1952 KB
02_rndhard_11.txt AC 54 ms 1948 KB
02_rndhard_12.txt AC 53 ms 1948 KB
02_rndhard_13.txt AC 53 ms 1952 KB
02_rndhard_14.txt AC 54 ms 2032 KB
02_rndhard_15.txt AC 54 ms 1960 KB
02_rndhard_16.txt AC 56 ms 1956 KB
02_rndhard_17.txt AC 54 ms 1952 KB
02_rndhard_18.txt AC 54 ms 1956 KB
02_rndhard_19.txt AC 53 ms 1960 KB
02_rndhard_20.txt AC 53 ms 1956 KB
02_rndhard_21.txt AC 54 ms 1948 KB
02_rndhard_22.txt AC 53 ms 1956 KB
02_rndhard_23.txt AC 53 ms 1944 KB
02_rndhard_24.txt AC 53 ms 1960 KB
02_rndhard_25.txt AC 53 ms 1960 KB
02_rndhard_26.txt AC 54 ms 1960 KB
02_rndhard_27.txt AC 53 ms 1956 KB
02_rndhard_28.txt AC 52 ms 1956 KB
02_rndhard_29.txt AC 52 ms 1956 KB
02_rndhard_30.txt AC 52 ms 1956 KB
02_rndhard_31.txt AC 52 ms 2012 KB
02_rndhard_32.txt AC 53 ms 1956 KB
02_rndhard_33.txt AC 52 ms 1948 KB
02_rndhard_34.txt AC 53 ms 1960 KB
02_rndhard_35.txt AC 53 ms 1956 KB
02_rndhard_36.txt AC 53 ms 1952 KB
02_rndhard_37.txt AC 53 ms 1952 KB
02_rndhard_38.txt AC 54 ms 1948 KB
02_rndhard_39.txt AC 53 ms 1952 KB
03_rndhardsmall_00.txt AC 25 ms 736 KB
03_rndhardsmall_01.txt AC 25 ms 800 KB
03_rndhardsmall_02.txt AC 25 ms 920 KB
03_rndhardsmall_03.txt AC 25 ms 796 KB
03_rndhardsmall_04.txt AC 26 ms 920 KB
03_rndhardsmall_05.txt AC 26 ms 920 KB
03_rndhardsmall_06.txt AC 25 ms 796 KB
03_rndhardsmall_07.txt AC 25 ms 800 KB
03_rndhardsmall_08.txt AC 25 ms 736 KB
03_rndhardsmall_09.txt AC 25 ms 736 KB