Submission #6257054

---

Source Code Expand

// https://atcoder.jp/contests/abc104/tasks/abc104_c

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>

using namespace std;

#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,a,n) for(int i=a;i<n;i++)
#define all(a) (a).begin(),(a).end()
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define eps 1e-15

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef map<int,int> mii;
typedef pair<int,int> pii;
typedef tuple<int,int,int> ti3;

// const int MOD_A = 1000000007;
// const int MOD_B = 1000000009;
// const int MOD_C = 998244353;

// 負の数にも対応した % 演算
ll mod(ll val, ll m) {
  ll res = val % m;
  if (res < 0) res += m;
  return res;
}

int H;
int W;
char C[510][510];
const int dxy[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

bool dfs(int x, int y)
{
    if (C[x][y] == 'g') {
        return true;
    }
    C[x][y] = '#';
    rep(i, 4)
    {
        int nx = x + dxy[i][0];
        int ny = y + dxy[i][1];
        if (nx >= 0 && nx < H && ny >= 0 && ny < W && C[nx][ny] != '#') {
            if(dfs(nx, ny)) return true;
        }
    }
    return false;
}

void Main()
{
    int sx, sy;
    cin >> H >> W;
    rep(i, H)
    {
        rep(j, W)
        {
            cin >> C[i][j];
            if (C[i][j] == 's') {
                sx = i;
                sy = j;
            }
        }
    }
    cout << (dfs(sx, sy) ? "Yes" : "No");
}

int main()
{
    cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	// cout << fixed << setprecision(15);
	Main();
}

Submission Info

Judge Result