제출 #530991

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
530991		Servus2022	Awesome Arrowland Adventure (eJOI19_adventure)	C++14	100 / 100	88 ms	22400 KiB

adventure

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

typedef pair < int, int > PII;

const int NMAX = 502, INF = 1e9;

const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};

char v[NMAX][NMAX];
int d[NMAX * NMAX], sel[NMAX * NMAX];
int N, M;

vector < PII > G[NMAX * NMAX];

auto cmp = [](PII a, PII b)
{
    if(!(a.first < b.first))
        return 1;
    return 0;
};
priority_queue <PII, vector <PII>, decltype(cmp)> H(cmp);

inline int code(PII a)
{
    if(!(1 <= a.first && a.first <= N && 1 <= a.second && a.second <= M))
        return 0;
    return (a.first - 1) * M + a.second;
}

inline void Read()
{
    cin.tie(nullptr);
    ios_base :: sync_with_stdio(false);

    cin >> N >> M;

    for(int i = 1; i <= N; ++i)
    {
        cin >> (v[i] + 1);

        for(int j = 1; j <= M; ++j)
        {
            if(v[i][j] == 'X')
                continue;

            PII est = {i, j + 1}, west = {i, j - 1}, sud = {i + 1, j}, nord = {i - 1, j};
            int ct = code({i, j});

            if(v[i][j] == 'E')
            {
                G[ct].push_back({0, code (est)});
                G[ct].push_back({1, code (sud)});
                G[ct].push_back({2, code (west)});
                G[ct].push_back({3, code (nord)});
            }
            if(v[i][j] == 'S')
            {
                G[ct].push_back({0, code (sud)});
                G[ct].push_back({1, code (west)});
                G[ct].push_back({2, code (nord)});
                G[ct].push_back({3, code (est)});
            }
            if(v[i][j] == 'W')
            {
                G[ct].push_back({0, code (west)});
                G[ct].push_back({1, code (nord)});
                G[ct].push_back({2, code (est)});
                G[ct].push_back({3, code (sud)});
            }
            if(v[i][j] == 'N')
            {
                G[ct].push_back({0, code (nord)});
                G[ct].push_back({1, code (est)});
                G[ct].push_back({2, code (sud)});
                G[ct].push_back({3, code (west)});
            }
        }
    }
    return;
}

inline void Dijkstra(int start)
{
    for(int i = 1; i <= N * M; ++i)
        d[i] = INF;

    for(auto it: G[start])
        if(it.second)
            H.push(it), d[it.second] = it.first;

    d[start] = 0;
    sel[start] = 1;

    while(!H.empty())
    {
        while(!H.empty() && sel[H.top().second])
            H.pop();
        if(H.empty())
            return;

        int node = H.top().second;
        sel[node] = 1;
        H.pop();

        for(auto it: G[node])
            if(it.second)
                if(d[node] + it.first < d[it.second])
                    d[it.second] = d[node] + it.first, H.push({d[it.second], it.second});
    }
    return;
}

int main()
{
    Read();
    Dijkstra(1);
    cout << (d[N * M] == INF ? -1 : d[N * M]) << '\n';
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 16 / 16
• Subtask 5: 50 / 50