Submission #10115029

---

Source Code Expand

#pragma region template

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


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>;

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[] = {make_pair(1, 0), make_pair(-1, 0), make_pair(0, -1),
                   make_pair(0, 1)};

#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))

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;
}

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


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);
}

struct setup_main {
    setup_main() {
        cin.tie(0);
        ios::sync_with_stdio(0);
        cout << fixed << setprecision(15);
    }
} setup_main_;


#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};
    int H, W;

    cin >> H >> W;
    vs c(H);

    rep(hi, H) {
        cin >>c[hi];
        if (in(c[hi], 's')) start = {hi, (int)(c[hi].find('s'))};
        if (in(c[hi], 'g')) goll = {hi, (int)(c[hi].find('g'))};
    }

    // solve;

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

    while (not(st.empty() or cangoll)) {
        point p = st.back();
        c[p.x][p.y] = wall;
        st.pop_back();
        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) {
                st.push_back(point{nx, ny});
                c[nx][ny] = wall;
            }
        }
    }

    if (cangoll == false) print("No");
    if (cangoll == true) print("Yes");

    return 0;
}

Submission Info

Judge Result