Submission #7137878

---

Source Code Expand

#include <string>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <bitset>
#include <stack>
using namespace std;

struct pos
{
    int x;
    int y;
    pos() {}
    pos(int _x, int _y)
    {
        x = _x; y = _y;
    }
};

int main()
{
    int h, w;
    cin >> h >> w;
    char** cell = new char*[h];
    bool** visited = new bool*[h];
    int s, g;
    for (int x = 0; x < h; x++)
    {
        cell[x] = new char[w];
        visited[x] = new bool[w];
        for (int y = 0; y < w; y++)
        {
            visited[x][y] = false;
            cin >> cell[x][y];
            if (cell[x][y] == 's')
            {
                s = x * 1000 + y;
            }
            else if (cell[x][y] == 'g')
            {
                g = x * 1000 + y;
            }
        }
    }

    stack<int> st;
    st.push(s);
    while (!st.empty())
    {
        int c = st.top();
        st.pop();
        int x = c / 1000, y = c % 1000;

        if (visited[x][y] || cell[x][y] == '#') continue;
        else if (cell[x][y] == 'g')
        {
            cout << "Yes" << endl;
            return 0;
        }
        visited[x][y] = true;

        if (x > 0) st.push((x - 1) * 1000 + y);
        if (y > 0) st.push(x * 1000 + (y - 1));
        if (x < h - 1) st.push((x + 1) * 1000 + y);
        if (y < w - 1) st.push(x * 1000 + (y + 1));
    }

    cout << "No" << endl;
    return 0;    
}

Submission Info

Judge Result