Submission #10093406

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#pragma region template

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vl = vector<ll>;
using vvl = vector<vl>;
using str = string;
using vs = vector<string>;
using vc = vector<char>;
using vvc = vector<vc>;

#define pb push_back
#define mp make_pair
#define F first
#define S second

#define reps(i, k, n) for (int i = (k), i##_len = (n); i < i##_len; ++i)
#define rep(i, n) reps(i, 0, n)
#define all(o) (o).begin(), (o).end()
#define sz(a) ((int)(a).size())
#define debug(x) cerr << x << " (L:" << __LINE__ << ")" << '\n';
#define bit(n) (1LL << (n))

const ll MOD = 1000000007;
const string YES = "Yes";
const string NO = "No";

const ll MAX = (ll)0x3f0000003f000000;
const double EPS = 1e-9;
const int dx[] = {0, 1, 0, -1, 1, -1, 1, -1},
          dy[] = {1, 0, -1, 0, 1, -1, -1, 1};
const pii dxy[] = {mp(1, 0), mp(-1, 0), mp(0, -1), mp(0, 1)};

ll mpow(ll a, ll b, ll m) {
    ll ans = 1;
    do {
        if (b & 1) ans = ans * a % m;
        a = a * a % m;
    } while (b >>= 1);  //  b/=2; }while (b!= 0);
    return ans;
}

inline ll mpow(ll a, ll b) {
    return mpow(a, b, MOD);
}

template <class T>
void print(T& x) {
    cout << x << '\n';
}

struct setup_main {
    setup_main() {
        cin.tie(0);
        ios::sync_with_stdio(0);
        cout << fixed << setprecision(15);
    }
} setup_main_;
inline bool in(string s, string c) {
    return (s.find(c) != string::npos);
}
inline bool in(string s, char c) {
    return (s.find(c) != string::npos);
}

#pragma endregion

struct point {
    int x;
    int y;
};

ll ans = 0;
const char wall = '#';
const char dot = '.';
signed main() {
    point start = {0, 0};
    point goll = {0, 0};
    // init
    int H, W;
    cin >> H >> W;
    vs c(H);
    rep(hi, H) {
        string ns;
        cin >> ns;
        c[hi] = ns;
        if (in(ns, 's')) start = {hi, (int)(ns.find('s'))};
        if (in(ns, 'g')) goll = {hi, (int)(ns.find('g'))};
    }

    // solve;

    deque<point> qu = {};
    qu.push_back(start);
    bool cangoll = false;

    while (not(qu.empty() or cangoll)) {

        point p = qu.front();
        qu.pop_front();
        rep(i, 4) {
            int nx = p.x + dx[i];
            int ny = p.y + dy[i];
            char nc;
            if (nx < 0 or H <= nx or ny < 0 or W <= ny) nc = wall;
            else
                nc = c[nx][ny];
            if (nc == 'g') cangoll = true;
            if (nc == dot) qu.push_back(point{nx, ny});
        }
        c[p.x][p.y] = wall;
    }

    if (cangoll == false) cout << "No\n";
    if (cangoll == true) cout << "Yes\n";

    return 0;
}

Submission Info

Judge Result