제출 #976374

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
976374		vjudge1	Awesome Arrowland Adventure (eJOI19_adventure)	C++17	0 / 100	1 ms	348 KiB

adventure

#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
• Subtask 2: 0 / 12
• Subtask 3: 0 / 12
• Subtask 4: 0 / 16
• Subtask 5: 0 / 50