Submission #3789528

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define FOR(I,X,Y) for(long long (I)=(X);(I)<(Y);(I)++)
#define REP(I,X,Y) for(long long (I)=(Y)-1;(I)>=(X);(I)--)
#define ALL(X) (X).begin(),(X).end()
#define pb push_back
#define COUNT(V,X) upper_bound((V).begin(),(V).end(),X)-lower_bound((V).begin(),(V).end(),X)
#define debug(x) cerr<<#x<<':'<<x<<endl;
#define DEBUG(v) cerr<<#v<<':';for(auto xXx:v)cerr<<xXx<<' ';cerr<<endl;
#define INF 1000000007
#define LINF 1000000000000000007
typedef long long ll;
typedef long double ld;
long long dx[] = {1,0,-1,0};
long long dy[] = {0,1,0,-1};
long long dx8[] = {1,1,0,-1,-1,-1,0,1};
long long dy8[] = {0,1,1,1,0,-1,-1,-1};
long long dx9[] = {1,1,0,-1,-1,-1,0,1,0};
long long dy9[] = {0,1,1,1,0,-1,-1,-1,0};

signed main(){
    ll H,W;
    cin >> H >> W;
    pair<ll,ll> s,g;
    char c[H][W];
    FOR(i,0,H)FOR(j,0,W){
        cin >> c[i][j];
        if(c[i][j] == 's')s = make_pair(i,j);
        if(c[i][j] == 'g')g = make_pair(i,j);
    }
    bool bfs[H][W];
    FOR(i,0,H)FOR(j,0,W)bfs[i][j] = 0;
    queue<pair<ll,ll>> que;
    que.push(s);
    bfs[s.first][s.second] = 1;
    while(que.size()){
        ll x = que.front().first,y = que.front().second;
        FOR(i,0,4){
            if(0 <= x+dx[i] && x+dx[i] < H && 0 <= y+dy[i] && y+dy[i] < W)
                if(bfs[x+dx[i]][y+dy[i]] == 0 && c[x+dx[i]][y+dy[i]] != '#'){
                    bfs[x+dx[i]][y+dy[i]] = 1;
                    que.push(make_pair(x+dx[i],y+dy[i]));
                }
        }
        que.pop();
    }
    if(bfs[g.first][g.second])cout << "Yes" << endl;
    else cout << "No" << endl;
}

Submission Info

Judge Result