Submission #1199836

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199836		badge881	Awesome Arrowland Adventure (eJOI19_adventure)	C++20	100 / 100	76 ms	8884 KiB

adventure

#include <bits/stdc++.h>
#define int long long
using namespace std;
int T, n, m;

signed main()
{
    scanf("%lld%lld", &n, &m);
    vector<vector<char>> v(n, vector<char>(m));
    for (auto &i : v)
        for (auto &j : i)
            scanf("\n %c", &j);
    vector<vector<int>> dist(n, vector<int>(m));
    for (auto &i : dist)
        for (auto &j : i)
            j = (int)1e18;
    dist[0][0] = 0;
    auto dir = [&](char from, int to) -> int
    {
        if (from == 'E')
        {
            array<int, 4> a = {0, 1, 2, 3};
            return a[to];
        }
        else if (from == 'S')
        {
            array<int, 4> a = {3, 0, 1, 2};
            return a[to];
        }
        else if (from == 'W')
        {
            array<int, 4> a = {2, 3, 0, 1};
            return a[to];
        }
        else
        {
            array<int, 4> a = {1, 2, 3, 0};
            return a[to];
        }
    };
    array<int, 4> dx = {0, 1, 0, -1};
    array<int, 4> dy = {1, 0, -1, 0};
    priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> q;
    q.push({0, {0, 0}});
    while (!q.empty())
    {
        pair<int, pair<int, int>> t = q.top();
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            int nx = t.second.first + dx[i];
            int ny = t.second.second + dy[i];
            auto [x, y] = t.second;
            if (v[x][y] == 'X')
                break;
            if (nx < 0 or nx > n - 1 or ny < 0 or ny > m - 1)
                continue;
            if (dist[nx][ny] > dist[x][y] + dir(v[x][y], i))
            {
                dist[nx][ny] = dist[x][y] + dir(v[x][y], i);
                q.push({dist[nx][ny], {nx, ny}});
            }
        }
    }
    printf("%lld\n", dist[n - 1][m - 1] == (int)1e18 ? -1 : dist[n - 1][m - 1]);
}

Compilation message (stderr)

adventure.cpp: In function 'int main()':
adventure.cpp:8:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 |     scanf("%lld%lld", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~
adventure.cpp:12:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |             scanf("\n %c", &j);
      |             ~~~~~^~~~~~~~~~~~~

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