Submission #423292

---

Source Code Expand

#include <iostream>
#include <vector>
#include <map>
#include <array>

using namespace std;

#define vi vector<int>
#define pii pair<int, int>

class Data
{
private:

    int m_height;
    int m_width;
    pii m_s_pos;
    pii m_g_pos;
    vector<vector<char>> m_field;
    vector<vector<int>> m_reached;

public:

    Data(vector<vector<char>> f, int h, int w, pii s, pii g) :
         m_field(f), m_height(h), m_width(w), m_s_pos(s), m_g_pos(g)
    {
        m_reached.resize(m_height);
        for (auto& it: m_reached) {
            it.resize(m_width);
        }
    }

    void dfs(const int cx, const int cy);
    void solve();
};

void Data::solve()
{
    this->dfs(m_s_pos.first, m_s_pos.second);
    
    if (m_reached.at(m_g_pos.second).at(m_g_pos.first)) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
}

void Data::dfs(const int cx, const int cy)
{
    // check

    if (cx < 0 || cx >= m_width || cy < 0 || cy >= m_height) return;

    if (m_field.at(cy).at(cx) == '#') return;

    if (m_reached.at(cy).at(cx)) return;

    // mark map
    m_reached.at(cy).at(cx) = true;

    // dfs
    const array<int, 4> dx = {0, 0, 1, -1};
    const array<int, 4> dy = {1, -1, 0, 0};
    
    for (int i = 0; i < 4; ++i) {
        int nx = cx + dx.at(i);
        int ny = cy + dy.at(i);
        
        this->dfs(nx, ny);
    }
}

int main()
{   
    ios::sync_with_stdio(false);

    // input
    int h, w;
    cin >> h >> w;

    vector<vector<char>> field(h, vector<char>(w));
    pii s, g;

    for (int y = 0; y < h; ++y) {
        for (int x = 0; x < w; ++x) {
            cin >> field.at(y).at(x);
            
            if (field.at(y).at(x) == 's') {
                s.first = x; s.second = y;
            } else if (field.at(y).at(x) == 'g') {
                g.first = x; g.second = y;
            }
        }
    }

    Data data(field, h, w, s, g);
    data.solve();

    return 0;
}

Submission Info

Judge Result