oj.uz

Submission #976374

# Submission time Handle Problem Language Result Execution time Memory
976374 2024-05-06T13:42:22 Z vjudge1 Awesome Arrowland Adventure (eJOI19_adventure) C++17
0 / 100
 1 ms 348 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define v(a) vector<a>
#define pll pair<ll, ll>
#define F first
#define S second

v(ll) dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};

int main(){
    ll n, m; cin >> n >> m;
    v(v(char)) arr(n, v(char)(m));
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++) cin >> arr[i][j];
    }

    queue<pll> temp;
    map<pll, bool> vis;

    temp.push({0, 0});
    vis[{0, 0}] = true;
    bool ok = false;
    while(!temp.empty()){
        ll x = temp.front().F, y = temp.front().S;
        temp.pop();
        if(x == n-1 && y == m-1){
            ok = true;
            break;
        }

        if(arr[x][y] == 'X') continue;

        for(int i = 0; i < 4; i++){
            ll xx = x+dx[i], yy = y+dy[i];
            if(xx < 0 || xx >= n || yy < 0 || yy >= m) continue;
            if(vis[{xx, yy}]) continue;
            vis[{xx, yy}] = true;
            temp.push({xx, yy});
        }
    }


    if(!ok) cout << -1;
    else {
        map<char, ll> base;
        base['N'] = 1;
        base['E'] = 2;
        base['S'] = 3;
        base['W'] = 4;
        base['X'] = 0;
        priority_queue<pair<pll, pll>, vector<pair<pll, pll>>, greater<pair<pll, pll>> > temp;
        ll ans = 1e9;
        temp.push({{0, -1}, {0, 0}});
        // ll cnt = 0;
        while(!temp.empty()){
            ll x = temp.top().S.F, y = temp.top().S.S, prev = temp.top().F.S;
            if(x == n-1 && y == m-1){
                ans = temp.top().F.F;
                break;
            }
            temp.pop();
            if(arr[x][y] == 'X') continue;
            // cnt++;
            // if(cnt >= 10) break;
            // cout << x << " " << y << endl;
            for(int i = 0; i < 4; i++){
                if(i == (prev+2)%4) continue;
                ll xx = x+dx[i], yy = y+dy[i];
                if(xx < 0 || xx >= n || yy < 0 || yy >= m) continue;
                // if(arr[xx][yy] == 'X') continue;
                ll dis = abs((n-1)-xx) + abs((m-1)-yy);
                // cout << base[arr[x][y]] << endl;
                ll rot = abs(base[arr[x][y]] - (i-1));
                // cout << rot << endl;
                // cout << xx << " " << yy << endl;
                // cout << dis << " " << rot << endl;
                temp.push({{dis+rot, i}, {xx, yy}});
            }
        }

        cout << ans;
    }
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 12.0

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

Subtask #3
0 / 12.0

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

Subtask #4
0 / 16.0

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

Subtask #5
0 / 50.0

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