Submission #5220052
Source Code Expand
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdalign>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
#define y0 qvya13579
#define y1 qvyb24680
#define j0 qvja13579
#define j1 qvjb24680
#define next qvne13579xt
#define prev qvpr13579ev
#define INF 1000000007
#define PI acos(-1.0)
#define endl "\n"
#define IOS cin.tie(0);ios::sync_with_stdio(false)
#define M_P make_pair
#define PU_B push_back
#define PU_F push_front
#define PO_B pop_back
#define PO_F pop_front
#define U_B upper_bound
#define L_B lower_bound
#define B_S binary_search
#define PR_Q priority_queue
#define FIR first
#define SEC second
#if __cplusplus < 201103L
#define stoi(argument_string) atoi((argument_string).c_str())
#endif
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define REP_R(i,n) for(int i=((int)(n)-1);i>=0;--i)
#define FOR(i,m,n) for(int i=((int)(m));i<(int)(n);++i)
#define FOR_R(i,m,n) for(int i=((int)(m)-1);i>=(int)(n);--i)
#define ALL(v) (v).begin(),(v).end()
#define RALL(v) (v).rbegin(),(v).rend()
#define SIZ(x) ((int)(x).size())
#define COUT(x) cout<<(x)<<endl
#define CIN(x) cin>>(x)
#define CIN2(x,y) cin>>(x)>>(y)
#define CIN3(x,y,z) cin>>(x)>>(y)>>(z)
#define CIN4(x,y,z,w) cin>>(x)>>(y)>>(z)>>(w)
#define SCAND(x) scanf("%d",&(x))
#define SCAND2(x,y) scanf("%d%d",&(x),&(y))
#define SCAND3(x,y,z) scanf("%d%d%d",&(x),&(y),&(z))
#define SCAND4(x,y,z,w) scanf("%d%d%d%d",&(x),&(y),&(z),&(w))
#define SCANLLD(x) scanf("%lld",&(x))
#define SCANLLD2(x,y) scanf("%lld%lld",&(x),&(y))
#define SCANLLD3(x,y,z) scanf("%lld%lld%lld",&(x),&(y),&(z))
#define SCANLLD4(x,y,z,w) scanf("%lld%lld%lld%lld",&(x),&(y),&(z),&(w))
#define PRINTD(x) printf("%d\n",(x))
#define PRINTLLD(x) printf("%lld\n",(x))
typedef long long int lli;
using namespace std;
bool compare_by_2nd(pair<int,int> a, pair<int,int> b)
{
if( a.second != b.second )
{
return a.second < b.second;
}
else
{
return a.first < b.first;
}
}
int ctoi(char c)
{
if( c >= '0' and c <= '9' )
{
return (int)(c-'0');
}
return -1;
}
int alphabet_pos(char c)
{
if( c >= 'a' and c <= 'z' )
{
return (int)(c-'a');
}
return -1;
}
int alphabet_pos_capital(char c)
{
if( c >= 'A' and c <= 'Z' )
{
return (int)(c-'A');
}
return -1;
}
vector<string> split(string str, char ch)
{
int first = 0;
int last = str.find_first_of(ch);
if(last == string::npos)
{
last = SIZ(str);
}
vector<string> result;
while( first < SIZ(str) )
{
string Ssubstr(str, first, last - first);
result.push_back(Ssubstr);
first = last + 1;
last = str.find_first_of(ch, first);
if(last == string::npos)
{
last = SIZ(str);
}
}
return result;
}
int gcd( int a , int b ) // assuming a,b >= 1
{
if( a < b )
{
return gcd( b , a );
}
if( a % b == 0 )
{
return b;
}
return gcd( b , a % b );
}
int lcm( int a , int b ) // assuming a,b >= 1
{
return a * b / gcd( a , b );
}
/*------------------ the end of the template -----------------------*/
void dfs( int iy_init , int ix_init , vector<string>& m , int H , int W )
{
deque<pair<int,int> > stack;
stack.push_back(make_pair(iy_init,ix_init));
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};
while( SIZ(stack) > 0 )
{
pair<int,int> temp = stack.back();
stack.pop_back();
m[temp.first][temp.second] = '#';
REP(i,4)
{
int y = temp.first + dy[i];
int x = temp.second + dx[i];
if( 0 <= y
and 0 <= x
and H > y
and W > x )
{
if( m[y][x] != '#')
{
stack.push_back(make_pair(y,x));
}
}
}
}
}
int main()
{
IOS; /* making cin faster */
int H,W;
CIN2(H,W);
vector<string> m(H);
int yg , xg;
int ys , xs;
REP(i,H)
{
CIN(m[i]);
REP(j,W)
{
if( m[i][j] == 'g' )
{
yg = i;
xg = j;
}
else if( m[i][j] == 's' )
{
ys = i;
xs = j;
}
}
}
dfs( ys , xs , m , H , W );
if( m[yg][xg] == '#' )
{
printf("Yes\n");
}
else
{
printf("No\n");
}
}
Submission Info
Submission Time |
|
Task |
A - 深さ優先探索 |
User |
yuyawk_0908 |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
6033 Byte |
Status |
AC |
Exec Time |
14 ms |
Memory |
2560 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
100 / 100 |
Status |
|
|
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 |
1 ms |
256 KB |
00_min_02.txt |
AC |
1 ms |
256 KB |
00_min_03.txt |
AC |
1 ms |
256 KB |
00_min_04.txt |
AC |
1 ms |
256 KB |
00_min_05.txt |
AC |
1 ms |
256 KB |
00_min_06.txt |
AC |
1 ms |
256 KB |
00_min_07.txt |
AC |
1 ms |
256 KB |
00_min_08.txt |
AC |
1 ms |
256 KB |
00_sample_01.txt |
AC |
1 ms |
256 KB |
00_sample_02.txt |
AC |
1 ms |
256 KB |
00_sample_03.txt |
AC |
1 ms |
256 KB |
00_sample_04.txt |
AC |
1 ms |
256 KB |
00_sample_05.txt |
AC |
1 ms |
256 KB |
01_rnd_00.txt |
AC |
2 ms |
512 KB |
01_rnd_01.txt |
AC |
13 ms |
2048 KB |
01_rnd_02.txt |
AC |
9 ms |
1024 KB |
01_rnd_03.txt |
AC |
14 ms |
2560 KB |
01_rnd_04.txt |
AC |
12 ms |
1920 KB |
01_rnd_05.txt |
AC |
2 ms |
512 KB |
01_rnd_06.txt |
AC |
9 ms |
896 KB |
01_rnd_07.txt |
AC |
9 ms |
896 KB |
01_rnd_08.txt |
AC |
2 ms |
512 KB |
01_rnd_09.txt |
AC |
2 ms |
512 KB |
01_rnd_10.txt |
AC |
6 ms |
640 KB |
01_rnd_11.txt |
AC |
2 ms |
512 KB |
01_rnd_12.txt |
AC |
11 ms |
1536 KB |
01_rnd_13.txt |
AC |
11 ms |
1408 KB |
01_rnd_14.txt |
AC |
2 ms |
512 KB |
01_rnd_15.txt |
AC |
8 ms |
640 KB |
01_rnd_16.txt |
AC |
2 ms |
512 KB |
01_rnd_17.txt |
AC |
7 ms |
640 KB |
01_rnd_18.txt |
AC |
2 ms |
512 KB |
01_rnd_19.txt |
AC |
13 ms |
2432 KB |
02_rndhard_00.txt |
AC |
2 ms |
512 KB |
02_rndhard_01.txt |
AC |
2 ms |
512 KB |
02_rndhard_02.txt |
AC |
3 ms |
512 KB |
02_rndhard_03.txt |
AC |
3 ms |
512 KB |
02_rndhard_04.txt |
AC |
2 ms |
512 KB |
02_rndhard_05.txt |
AC |
2 ms |
512 KB |
02_rndhard_06.txt |
AC |
2 ms |
512 KB |
02_rndhard_07.txt |
AC |
2 ms |
512 KB |
02_rndhard_08.txt |
AC |
3 ms |
512 KB |
02_rndhard_09.txt |
AC |
3 ms |
512 KB |
02_rndhard_10.txt |
AC |
3 ms |
512 KB |
02_rndhard_11.txt |
AC |
3 ms |
512 KB |
02_rndhard_12.txt |
AC |
2 ms |
512 KB |
02_rndhard_13.txt |
AC |
2 ms |
512 KB |
02_rndhard_14.txt |
AC |
3 ms |
512 KB |
02_rndhard_15.txt |
AC |
3 ms |
512 KB |
02_rndhard_16.txt |
AC |
2 ms |
512 KB |
02_rndhard_17.txt |
AC |
2 ms |
512 KB |
02_rndhard_18.txt |
AC |
2 ms |
512 KB |
02_rndhard_19.txt |
AC |
2 ms |
512 KB |
02_rndhard_20.txt |
AC |
2 ms |
512 KB |
02_rndhard_21.txt |
AC |
2 ms |
512 KB |
02_rndhard_22.txt |
AC |
2 ms |
512 KB |
02_rndhard_23.txt |
AC |
2 ms |
512 KB |
02_rndhard_24.txt |
AC |
2 ms |
512 KB |
02_rndhard_25.txt |
AC |
2 ms |
512 KB |
02_rndhard_26.txt |
AC |
2 ms |
512 KB |
02_rndhard_27.txt |
AC |
2 ms |
512 KB |
02_rndhard_28.txt |
AC |
2 ms |
512 KB |
02_rndhard_29.txt |
AC |
2 ms |
512 KB |
02_rndhard_30.txt |
AC |
2 ms |
512 KB |
02_rndhard_31.txt |
AC |
2 ms |
512 KB |
02_rndhard_32.txt |
AC |
2 ms |
512 KB |
02_rndhard_33.txt |
AC |
2 ms |
512 KB |
02_rndhard_34.txt |
AC |
2 ms |
512 KB |
02_rndhard_35.txt |
AC |
2 ms |
512 KB |
02_rndhard_36.txt |
AC |
2 ms |
512 KB |
02_rndhard_37.txt |
AC |
2 ms |
512 KB |
02_rndhard_38.txt |
AC |
2 ms |
512 KB |
02_rndhard_39.txt |
AC |
2 ms |
512 KB |
03_rndhardsmall_00.txt |
AC |
1 ms |
256 KB |
03_rndhardsmall_01.txt |
AC |
1 ms |
256 KB |
03_rndhardsmall_02.txt |
AC |
1 ms |
256 KB |
03_rndhardsmall_03.txt |
AC |
1 ms |
256 KB |
03_rndhardsmall_04.txt |
AC |
1 ms |
256 KB |
03_rndhardsmall_05.txt |
AC |
1 ms |
256 KB |
03_rndhardsmall_06.txt |
AC |
1 ms |
256 KB |
03_rndhardsmall_07.txt |
AC |
1 ms |
256 KB |
03_rndhardsmall_08.txt |
AC |
1 ms |
256 KB |
03_rndhardsmall_09.txt |
AC |
1 ms |
256 KB |