oj.uz

Submission #976385

# Submission time Handle Problem Language Result Execution time Memory
976385 2024-05-06T13:51:48 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;
            string awal = "NESW";
            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 = ((i+1)-base[arr[x][y]]+4)%4;
                    // 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 348 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 #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 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 #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 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 344 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 348 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 -