Submission #11422762

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define all(x) (x).begin(),(x).end()
#define rep(i, n) for(ll i = 0; i < n; i++)
const ll INF = 100100100100;


ll combination(ll n, ll r){
    if(n < r) return 0;
    if(r == 0||r == n) return 1;
    else if(r == 1) return n;
    return (combination(n - 1, r - 1) + combination(n - 1, r));
}

bool checkKaibun(string str){
    string checkStr = str;
    reverse(checkStr.begin(), checkStr.end());
    if(str == checkStr) return true;
    else return false;
}

int keta(ll num){
    int digits = 0;
    while(num > 0){
        num /= 10;
        digits++;
    }
    return digits;
}


int main(){
    int H, W;
    cin >> H >> W;
    int sx, sy, gx, gy;
    vector<vector<char>> m(H, vector<char>(W));
    rep(i, H){
        rep(j, W){
            cin >> m[i][j];
            if(m[i][j] == 's'){
                sx = i;
                sy = j;
            }
            if(m[i][j] == 'g'){
                gx = i;
                gy = j;
            }
        }
    }

    vector<vector<int>> dist(H, vector<int>(W, -1));
    stack<vector<int>> sta;
    dist[sx][sy] = 0;
    sta.push({sx, sy});
    while(!sta.empty()){
        vector<int> v = sta.top(); sta.pop();
        if(v[0] + 1 < H){
            if(dist[v[0] + 1][v[1]] == -1 && m[v[0] + 1][v[1]] != '#'){
                dist[v[0] + 1][v[1]] = dist[v[0]][v[1]] + 1;
                sta.push({v[0] + 1, v[1]});
            }
        }
        if(v[0] - 1 > -1){
            if(dist[v[0] - 1][v[1]] == -1 && m[v[0] - 1][v[1]] != '#'){
                dist[v[0] - 1][v[1]] = dist[v[0]][v[1]] + 1;
                sta.push({v[0] - 1, v[1]});
            }
        }
        if(v[1] + 1 < W){
            if(dist[v[0]][v[1] + 1] == -1 && m[v[0]][v[1] + 1] != '#'){
                dist[v[0]][v[1] + 1] = dist[v[0]][v[1]] + 1;
                sta.push({v[0], v[1] + 1});
            }
        }
        if(v[1] - 1 > -1){
            if(dist[v[0]][v[1] - 1] == -1 && m[v[0]][v[1] - 1] != '#'){
                dist[v[0]][v[1] - 1] = dist[v[0]][v[1]] + 1;
                sta.push({v[0], v[1] - 1});
            }
        }
    }
    if(dist[gx][gy] == -1)cout << "No" << endl;
    else cout << "Yes" << endl;
}

Submission Info

Judge Result