oj.uz

Submission #962588

# Submission time Handle Problem Language Result Execution time Memory
962588 2024-04-13T22:24:25 Z AtabayRajabli Awesome Arrowland Adventure (eJOI19_adventure) C++17
0 / 100
 1 ms 348 KB 
#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++;
            }
        }
    }

    cout << d[n][m];
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -