Submission #962590

#	Time	Username	Problem	Language	Result	Execution time	Memory
962590		AtabayRajabli	Awesome Arrowland Adventure (eJOI19_adventure)	C++17	100 / 100	20 ms	8536 KiB

adventure

#include <bits/stdc++.h>

// author : a1abay

#define all(v)      v.begin(), v.end()
#define GCD(a, b)   __gcd(a, b)
#define LCM(a, b)   (a*b / (__gcd(a, b)))
#define int         ll

typedef long long           ll;
const int inf =             1e9 + 7;
const int inff =            (int)1e18 + 7;
const int sz =              5e2 + 5;
using namespace             std;

int n, m;
int a[sz][sz];

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

bool ok(int x, int y)
{
    return 1 <= x && x <= n && 1 <= y && y <= m;
}

signed main()   
{       
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    map<char, int> mp;
    mp['N'] = 0;
    mp['E'] = 1;
    mp['S'] = 2;
    mp['W'] = 3;
    mp['X'] = 4;
    
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            char c;
            cin >> c;
            a[i][j] = mp[c];
        }
    }

    queue<array<int, 2>> q[4];
    q[0].push({1, 1});
    vector<vector<int>> d(n + 1, vector<int>(m + 1, inf));
    d[1][1] = 0;
    int pos = 0, num = 1;
    
    while(num > 0)
    {
        while(q[pos].empty())
        {
            pos = (pos + 1) % 4;
        }
        int x = q[pos].front()[0], y = q[pos].front()[1];
        q[pos].pop();
        num--;
        if(a[x][y] == 4)continue;
        for(int i = 0; i < 4; i++)
        {
            int vx = dx[i] + x;
            int vy = dy[i] + y;
            if(!ok(vx, vy))continue;
            int w = (i <= a[x][y] ? (i + 4 - a[x][y]) % 4 : i - a[x][y]);
            
            if(d[vx][vy] > d[x][y] + w)
            {
                d[vx][vy] = d[x][y] + w;
                q[d[vx][vy] % 4].push({vx, vy});
                num++;
            }
        }
    }
    if(d[n][m] >= inf)d[n][m] = -1;
    cout << d[n][m];
}

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