Submission #530982

#	Time	Username	Problem	Language	Result	Execution time	Memory
530982		Servus2022	Awesome Arrowland Adventure (eJOI19_adventure)	C++14	0 / 100	4 ms	6240 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;
    if(v[a.first][a.second] == 'X' && (a.first != N || a.second != M))
        return 0;
    return (a.first - 1) * M + a.second;
}

inline PII decode(int x)
{
    if(x % M == 0)
        return {x / M, M};
    return {x / M, x % M};
}

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' && (i != N || j != M))
                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 <= code({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[code({N, M})] << '\n';
    return 0;
}

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