Submission #919443

#	Time	Username	Problem	Language	Result	Execution time	Memory
919443		raphaelp	Awesome Arrowland Adventure (eJOI19_adventure)	C++14	100 / 100	88 ms	15604 KiB

adventure

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int M, N;
    cin >> M >> N;
    vector<string> Tab(M);
    for (int i = 0; i < M; i++)
    {
        cin >> Tab[i];
        for (int j = 0; j < N; j++)
        {
            if (Tab[i][j] == 'W')
                Tab[i][j] = '0';
            if (Tab[i][j] == 'N')
                Tab[i][j] = '3';
            if (Tab[i][j] == 'E')
                Tab[i][j] = '2';
            if (Tab[i][j] == 'S')
                Tab[i][j] = '1';
        }
    }
    vector<vector<int>> occ(M, vector<int>(N, 1000000000));
    priority_queue<vector<int>> Q;
    vector<int> transX = {0, -1, 0, 1}, transY = {-1, 0, 1, 0}, co = {2, 3, 0, 1};
    Q.push({0, M - 1, N - 1});
    occ[M - 1][N - 1] = 0;
    while (!Q.empty())
    {
        int x = Q.top()[1];
        int y = Q.top()[2];
        int dist = -Q.top()[0];
        Q.pop();
        if (dist > occ[x][y])
            continue;
        if (x == 0 && y == 0)
        {
            cout << dist;
            return 0;
        }

        for (int i = 0; i < 4; i++)
        {
            if (x + transX[i] < 0 || x + transX[i] >= M || y + transY[i] < 0 || y + transY[i] >= N)
                continue;
            if (Tab[x + transX[i]][y + transY[i]] == 'X')
                continue;
            int cost = (co[i] + Tab[x + transX[i]][y + transY[i]] - '0') % 4;
            if (dist + cost < occ[x + transX[i]][y + transY[i]])
            {
                occ[x + transX[i]][y + transY[i]] = dist + cost;
                Q.push({-dist - cost, x + transX[i], y + transY[i]});
            }
        }
    }
    cout << -1;
}

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