Submission #10258631

---

Source Code Expand

#include "bits/stdc++.h"
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;

typedef long long ll;

int main() {
    int H, W, si, sj, gi, gj;
    cin >> H >> W;
    string c;
    vector<vector<bool>> done(H + 2, vector<bool>(W + 2, true));
    rep(i, H) {
        cin >> c;
        rep(j, W) {
            done[i + 1][j + 1] = false;
            if (c[j] == 's') {
                si = i + 1;
                sj = j + 1;
            }
            if (c[j] == 'g') {
                gi = i + 1;
                gj = j + 1;
            }
            if (c[j] == '#') done[i + 1][j + 1] = true;
        }
    }
    queue<pair<int, int>> q;
    q.push(make_pair(si, sj));
    while (q.size() > 0) {
        auto p = q.front();
        q.pop();
        int i = p.first, j = p.second;
        if (done[i][j]) continue;
        done[i][j] = true;
        int di[4] = {1, 0, -1, 0}, dj[4] = {0, 1, 0, -1};
        rep(k, 4) {
            int ni = i + di[k], nj = j + dj[k];
            if (ni == gi && nj == gj) {
                cout << "Yes\n";
                return 0;
            }
            if (!done[ni][nj]) q.push(make_pair(ni, nj));
        }
    }
    cout << "No\n";
}

Submission Info

Judge Result