Submission #420219

---

Source Code Expand

// standard i/o
#include <iostream>
#include <sstream>
#include <cstdio>
// standard library
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>
// template class
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
// container control
#include <algorithm>

using namespace std;

#define rep( i, n ) for( int i = 0; i < n; ++i )
#define irep( i, n ) for( int i = n-1; i >= 0; --i )
#define reep( i, s, n ) for ( int i = s; i < n; ++i )
#define ireep( i, n, s ) for ( int i = n-1; i >= s; --i )
#define foreach(itr, x) for( typeof(x.begin()) itr = x.begin(); itr != x.end(); ++itr)

#define mp( a, b ) make_pair( a, b )
#define pb( a ) push_back( a )
#define all( v ) v.begin(), v.end()
#define fs first
#define sc second
#define vc vector

typedef long long ll;
typedef complex<double> point;

typedef pair<int, int> pii;
typedef pair<int, pii> ipii;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector< vector<int> > vii;
typedef vector< vector<double> > vdd;

typedef vector<int>::iterator vi_itr;

const int iinf = 1 << 28;
const double inf = 1e30;
const double eps = 1e-10;
const double pi = acos(-1.0);

// direction : l u r d
const int dx[] = { -1, 0, 1, 0};
const int dy[] = { 0, -1, 0, 1 };

int h, w;
char field[500][500];
bool visited[500][500];
pii start, goal;

bool search ( int x, int y )
{
	visited[y][x] = true;
	
	if( field[y][x] == 'g' ){
		return true;
	}
	
	bool ret = false;

	rep(i, 4){
		int nx = x + dx[i];
		int ny = y + dy[i];

		if( nx < 0 || nx >= w || ny < 0 || ny >= h ){
			continue;
		}
		if( visited[ny][nx] || field[ny][nx] == '#' ){
			continue;
		}

		ret |= search(nx, ny);
	}

	return ret;
}

int main()
{
	cin >> h >> w;
	rep(i, h){
		rep(j, w){
			cin >> field[i][j];
			if( field[i][j] == 's' ){
				start = mp(j, i);
			}
			else if( field[i][j] == 'g' ){
				goal = mp(j, i);
			}
		}
	}

	cout << (search(start.fs, start.sc) ? "Yes" : "No") << endl;
}

Submission Info

Judge Result