Submission #420196

---

Source Code Expand

#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <functional>
#include <iostream>
#include <iomanip>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <utility>
#include <vector>

using namespace std;

typedef long long Long;
#define whole(xs) xs.begin(), xs.end()
#define uniq(xs) (xs.erase(unique(xs.begin(), xs.end()), xs.end()))

template<class T>
ostream& operator<<(ostream& os, const vector<T>& vs) {
    if (vs.empty()) return os << "[]";
    os << "[" << vs[0];
    for (int i = 1; i < vs.size(); i++) os << " " << vs[i];
    return os << "]";
}

const int IINF = 1<<28;
const Long LINF = 1LL<<56;
#define INF IINF

int H, W;
vector<string> F;
void Input() {
    cin >> H >> W;
    F.clear(); F.resize(H);
    for (int i = 0; i < H; i++) cin >> F[i];
}

int sy, sx;

const int dy[] = {-1, 0, 1, 0}, dx[] = {0, 1, 0, -1};

const int MAX_H = 501, MAX_W = 501;
bool used[MAX_H][MAX_W];
bool dfs(int y, int x) {
    if (F[y][x] == 'g') return true;
    used[y][x] = true;
    for (int i = 0; i < 4; i++) {
        int ny = y + dy[i],
            nx = x + dx[i];
        if (ny < 0 || ny >= H) continue;
        if (nx < 0 || nx >= W) continue;
        if (F[ny][nx] == '#') continue;
        if (used[ny][nx]) continue;
        if (dfs(ny, nx)) return true;
    }
    return false;
}

void Solve() {
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            if (F[i][j] == 's') {
                sy = i;
                sx = j;
            }
        }
    }
    memset(used, 0, sizeof(used));
    cout << (dfs(sy, sx) ? "Yes" : "No") << endl;
}

int main() {
    Input(); Solve();
    return 0;
}

Submission Info

Judge Result