Submission #464557

#	Time	Username	Problem	Language	Result	Execution time	Memory
464557		ewirlan	Awesome Arrowland Adventure (eJOI19_adventure)	C++17	100 / 100	89 ms	5432 KiB

adventure

//Awesome Arrowland Adventure

#define _CTR_SECURE_NO_WARNINGS
#include <iostream>
#include <queue>
#include <utility>
#include <functional>
typedef long long int ll;
enum Kier
{
    N, E, S, W, M,
};
template <typename T> T in()
{
    T x;
    std::cin >> x;
    return x;
}
Kier in()
{
    char c(in<char>());
    switch (c)
    {
    case 'N':
        return N;
        break;
    case 'E':
        return E;
        break;
    case 'S':
        return S;
        break;
    case 'W':
        return W;
        break;
    default:
        return M;
        break;
    }
}
inline Kier ruch(Kier z, Kier d)
{
    return static_cast<Kier>((M + d - z) % M);
}
constexpr int maxn = 503;
int odp[maxn][maxn];
Kier arr[maxn][maxn];
int main()
{
    std::cin.tie(nullptr); std::cout.tie(nullptr); std::ios_base::sync_with_stdio(0);
    int n(in<int>()), m(in<int>());
    for (int i(0); i < n; ++i)for (int j(0); j < m; ++j)
    {
        Kier k(in());
        if (k == M) { if (i < n - 1 || j < m - 1)odp[i][j] = 1; }
        else arr[i][j] = k;
    }
    if (odp[0][0])
    {
        std::cout << -(n > 1 || m > 1) << '\n';
        return 0;
    }
    std::priority_queue <std::pair <int, std::pair <int, int>>> kul;
    kul.push({ -1,{ n - 1, m - 1 } });
    while (kul.size())
    {
        std::function <bool(int x, int y)> ok([n, m](int x, int y) -> bool
            {
                if (x < 0 || y < 0 || x >= n || y >= m)return 0;
                return !odp[x][y];
            });
        int x(kul.top().second.first);
        int y(kul.top().second.second);
        int odl(kul.top().first);
        kul.pop();
        if (odp[x][y])continue;
        odp[x][y] = odl;
        if (ok(x - 1, y))kul.push({odl - ruch(arr[x - 1][y], S), {x - 1, y} });
        if (ok(x + 1, y))kul.push({odl - ruch(arr[x + 1][y], N), {x + 1, y} });
        if (ok(x, y - 1))kul.push({odl - ruch(arr[x][y - 1], E), {x, y - 1} });
        if (ok(x, y + 1))kul.push({odl - ruch(arr[x][y + 1], W), {x, y + 1} });
    }
    std::cout << -odp[0][0] - 1 << '\n';
    return 0;
}

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