Submission #1222970

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222970		khome	Awesome Arrowland Adventure (eJOI19_adventure)	C++20	100 / 100	72 ms	21248 KiB

adventure

#include <bits/stdc++.h>
using namespace std;
// #define int long long

const int INF = 1e9;

void solve(){
    int n, m; cin >> n >> m;
    vector<char> v(n*m);
    vector<vector<pair<int, int>>> adj(n*m);
    // vector<int> dis(n*m, INF);
    
    for (int i = 0; i < n ; i++){
        for (int j = 0; j < m; j++) {
            cin >> v[i*m+j];
        }
    }

    map<pair<char, char>, int> mp;
    mp[{'E', 'E'}] = 0;
    mp[{'N', 'E'}] = 1;
    mp[{'W', 'E'}] = 2;
    mp[{'S', 'E'}] = 3;

    mp[{'S', 'S'}] = 0;
    mp[{'E', 'S'}] = 1;
    mp[{'N', 'S'}] = 2;
    mp[{'W', 'S'}] = 3;

    mp[{'W', 'W'}] = 0;
    mp[{'S', 'W'}] = 1;
    mp[{'E', 'W'}] = 2;
    mp[{'N', 'W'}] = 3;

    mp[{'N', 'N'}] = 0;
    mp[{'W', 'N'}] = 1;
    mp[{'S', 'N'}] = 2;
    mp[{'E', 'N'}] = 3;

    for (int i = 0; i < n; i++){
        for (int j = 0; j < m; j++){
            if (v[i*m+j] == 'X')continue;
            for (int dx = -1; dx <= 1; dx++){
                for (int dy = -1; dy <= 1; dy++){
                    if (abs(dx) + abs(dy) == 1) {
                        int a = i+dx, b = j+dy;
                        if (a < 0 || b < 0 || a >= n || b >= m) continue;
                        // if (v[a*m+b] == 'X') continue;
                        char using_c = '-';
                        if(dx == 1) using_c = 'S';
                        if(dx == -1) using_c = 'N';
                        if(dy == 1) using_c = 'E';
                        if(dy == -1) using_c = 'W';
                        adj[i * m + j].push_back({a * m + b,  mp[{v[i * m + j], using_c}]});
                    }
                }
            }
        }
    }

    vector<int> dis(n*m, INF);
    priority_queue<pair<int, int>> pq;
    dis[0] = 0;
    pq.push({0, 0});
    while (!pq.empty()){
        auto [c, a] = pq.top(); pq.pop();
        if (dis[a] != -c) continue;
        for (auto [ch, ch_w] : adj[a]){
            if (dis[a] + ch_w < dis[ch]) {
                dis[ch] = dis[a] + ch_w;
                pq.push({-dis[ch], ch});
            }
        }
    }
    if (dis[n*m-1] == INF) dis[n*m-1] = -1;
    // for (auto [b, c] : adj[2]){
    //     cout <<b << ' ' <<  c << endl;
    // }
    cout << dis[n*m-1] << endl;
}


signed main() {
    ios_base::sync_with_stdio(0);
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
	int t = 1; 
    // cin >> t;
    while (t--){solve();}
}

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