Submission #11420764

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using mii = map<int, int>;
const int INF = 1e9;
const ll LINF = 1e18;
#define MP(a,b) make_pair((a),(b))
#define MT(...) make_tuple(__VA_ARGS__)

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define REPS(i,x) for(int i=1;i<=(int)(x);i++)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define RREPS(i,x) for(int i=((int)(x));i>0;i--)

#define ALL(x) (x).begin(),(x).end()
#define IN(type,a) type a;cin >> a
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define COUT(x) cout << (x) << endl
#define DCOUT(x,n) cout << fixed << setprecision(n) << (x) << endl
int h,w;
vector<vector<char>> c(500,vector<char>(500));
vector<vector<bool>> a(500,vector<bool>(500,false));

void DFS(int y, int x){
    a[y][x] = true;
    if (x<w-1) {
        if (!a[y][x+1]&&((c[y][x+1]=='.')||(c[y][x+1]=='g'))) {
            DFS(y,x+1);
        }
    }
    if (y<h-1) {
        if (!a[y+1][x]&&((c[y+1][x]=='.')||(c[y+1][x]=='g'))) {
            DFS(y+1,x);
        }
    }
    if (x>0) {
        if (!a[y][x-1]&&((c[y][x-1]=='.')||(c[y][x-1]=='g'))) {
            DFS(y,x-1);
        }
    }
    if (y>0) {
        if (!a[y-1][x]&&((c[y-1][x]=='.')||(c[y-1][x]=='g'))) {
            DFS(y-1,x);
        }
    }
    return;
}

int main() {
    cin >> h >> w;
    int s1,s2;
    int g1,g2;
    REP(i, h){
        REP(j, w){
            cin >> c[i][j];
            if (c[i][j]=='s') {
                s1=i;
                s2=j;
            }else if (c[i][j]=='g') {
                g1=i;
                g2=j;
            }
        }
    }
    DFS(s1, s2);
    Yes(a[g1][g2]);
}

Submission Info

Judge Result