Submission #2829191

---

Source Code Expand

#if !defined(__clang__) && defined(__GNUC__)
#include <bits/stdc++.h>
#else
#include <cstdlib>
#include <climits>
#include <iostream>
#include <cstdint>
#include <vector>
#include <string>
#include <complex>
#include <bitset>
#include <queue>
#include <deque>
#include <stack>
#include <utility>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <regex>
#endif //  !defined(__clang__) && defined(__GNUG__)
#include <boost/lexical_cast.hpp>
#include <boost/algorithm/string.hpp>
#include <boost/multi_array.hpp>
#include <boost/optional.hpp>
#include <boost/math/common_factor_rt.hpp>

using namespace std;


int main()
{
    int64_t H, W;
    std::cin >> H >> W;

    boost::multi_array<char, 2> C(boost::extents[H][W]);

    for (auto p = C.data(); p < (C.origin() + C.num_elements()); ++p) {
        std::cin >> *p;
    }

    auto f = [&C, H, W](auto y0, auto x0) -> void {
        using axis_t = decltype(x0);

        std::queue<std::pair<axis_t, axis_t>> q;

        // setup initilal position
        q.push({y0, x0});

        C[y0][x0] = '#';

        while (!q.empty()) {

            axis_t x, y;

            std::tie(y, x) = q.front();
            q.pop();

            // 四方に動くパターン
            constexpr std::pair<int, int> dirs4[] = {{1, 0}, {0, -1}, {-1, 0}, {0, 1}};
            for (auto dir: dirs4) {
                auto xx = x + dir.first;
                auto yy = y + dir.second;
                if (0 <= xx && xx < W && 0 <= yy && yy < H) {
                    if (C[yy][xx] == 'g') {
                        std::cout << "Yes" << std::endl;
                        return;
                    }
                    else if (C[yy][xx] == '.') {
                        C[yy][xx] = '#';
                        q.push({yy, xx});
                    }
                }
            }
        } // while()

        // 終了条件にマッチせず探索終了
        std::cout << "No" << std::endl;
    };

    for (int y = 0; y < H; ++y) {
        for (int x = 0; x < W; ++x) {
            if (C[y][x] == 's') {
                f(y, x);
                return 0;
            }
        }
    }

    return 0;
}

Submission Info

Judge Result