Submission #11227863

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(begin, i, end) for (int i = begin; i < (int)(end); i++)
#define all(v) v.begin(), v.end()
const int MOD = 1000000007;

int H, W;
int sx, sy, gx, gy;
vector<vector<bool>> seen(510, vector<bool>(510, false));
vector<vector<char>> road(510, vector<char>(510, '.'));

bool dfs(int x, int y, int count);

int main()
{
    // データの受け取り
    cin >> H >> W;
    rep(0, i, H)
    {
        rep(0, j, W)
        {
            char a;
            cin >> a;
            if (a == 's') // スタート地点
            {
                sx = i;
                sy = j;
            }
            else if (a == 'g') // ゴール地点
            {
                gx = i;
                gy = j;
            }
            else if (a == '#')
            {
                road.at(i).at(j) = '#';
            }
        }
    }

    /*
    //　入力が正しくできているか確認
    cout << sx << ' ' << sy << endl;
    cout << gx << ' ' << gy << endl;
    rep(0, i, H)
    {
        rep(0, j, W)
        {
            cout << road.at(i).at(j);
        }
        cout << endl;
    }
    */

    // dfsの結果から出力を決定
    if (dfs(sx, sy, 0))
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
}

bool dfs(int x, int y, int count)
{
    // ゴールについたら
    if ((x == gx) && (y == gy))
    {
        return true;
    }
    // はみ出したり塀に当たったら
    else if ((x < 0) || (H - 1 < x) || (y < 0) || (W - 1 < y) || (road.at(x).at(y) == '#'))
    {
        return false;
    }
    // 探索済みなら
    if (seen.at(x).at(y))
    {
        return false;
    }
    // 探索済みの印をつける
    else
    {
        seen.at(x).at(y) = true;
    }
    // それらのどれでもないとき
    return (dfs(x + 1, y, count + 1) || dfs(x - 1, y, count + 1) || dfs(x, y + 1, count + 1) || dfs(x, y - 1, count + 1));
}

Submission Info

Judge Result