Submission #27475

---

Source Code Expand

#include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;

bool solve(int w, int h, const vector< string >& maze)
{
    vector< vector< int > > score(h, vector< int >(w, 3));
    pair< int, int > s, g;
    for (int y = 0; y < h; ++y)
    {
        for (int x = 0; x < w; ++x)
        {
            if (maze[y][x] == 's') s = pair< int, int >(x, y);
            if (maze[y][x] == 'g') g = pair< int, int >(x, y);
        }
    }
    stack< pair< int, int > > stack;
    stack.push(s);
    score[s.second][s.first] = 0;
    while (!stack.empty())
    {
        pair< int, int > p = stack.top();
        stack.pop();
        if (p == g && score[p.second][p.first] < 3) return true;
        vector< pair< int, int > > ps;
        ps.push_back(pair< int, int >(p.first, p.second-1));
        ps.push_back(pair< int, int >(p.first, p.second+1));
        ps.push_back(pair< int, int >(p.first-1, p.second));
        ps.push_back(pair< int, int >(p.first+1, p.second));
        for (vector< pair< int, int > >::iterator i = ps.begin();
             i != ps.end(); ++i)
        {
            if (i->first < 0|| w <= i->first || i->second < 0 || h <= i->second) continue;
            if (maze[i->second][i->first] == '#')
            {
                if (score[i->second][i->first] > score[p.second][p.first] + 1)
                {
                    score[i->second][i->first] = score[p.second][p.first] + 1;
                    stack.push(*i);
                }
            }
            else
            {
                if (score[i->second][i->first] > score[p.second][p.first])
                {
                    score[i->second][i->first] = score[p.second][p.first];
                    stack.push(*i);
                }
            }
        }
    }
    return false;
}

int main()
{
    int w, h;
    cin >> h >> w;
    string null;
    getline(cin, null);
    vector< string > maze(h);
    for (int i = 0; i < h; ++i) getline(cin, maze[i]);
    cout << (solve(w,h,maze) ? "YES" : "NO") << endl;
    return 0;
}

Submission Info

Judge Result