Submission #947577

#	Time	Username	Problem	Language	Result	Execution time	Memory
947577		speedcode	Awesome Arrowland Adventure (eJOI19_adventure)	C++17	100 / 100	55 ms	2204 KiB

adventure

#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
const int INF = 1000000007;
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int m,n;
    cin >> m >> n;
    set<pair<int, pair<int, int>>> cache;
    char board[m][n];
    int distances[m][n];
    bool fixed[m][n];
    for(int i = 0; i < m; i++){
        for(int j = 0; j < n; j++){
            cin >> board[i][j];
            distances[i][j] = INF;
            fixed[i][j] = 0;
        }
    }
    //Dijkstra !
    distances[0][0] = 0;
    cache.insert({0, {0,0}});

    while(cache.size()){
        auto k = *cache.begin();
        cache.erase(cache.begin());
        if(board[k.second.first][k.second.second] == 'X') {
            fixed[k.second.first][k.second.second] = 1;
            continue;
        }
        
        // E
        if(board[k.second.first][k.second.second] == 'E') {
            fixed[k.second.first][k.second.second] = 1;
            if(k.second.second < n-1 && !fixed[k.second.first][k.second.second+1] 
            && distances[k.second.first][k.second.second+1] > distances[k.second.first][k.second.second] + 0){
                cache.erase({distances[k.second.first][k.second.second+1], {k.second.first, k.second.second+1}});
                distances[k.second.first][k.second.second+1] = distances[k.second.first][k.second.second] + 0;
                cache.insert({distances[k.second.first][k.second.second+1], {k.second.first, k.second.second+1}});
            }
            // S
            if(k.second.first < m-1 && !fixed[k.second.first+1][k.second.second] 
            && distances[k.second.first+1][k.second.second] > distances[k.second.first][k.second.second] + 1){
                cache.erase({distances[k.second.first+1][k.second.second], {k.second.first+1, k.second.second}});
                distances[k.second.first+1][k.second.second] = distances[k.second.first][k.second.second] + 1;
                cache.insert({distances[k.second.first+1][k.second.second], {k.second.first+1, k.second.second}});
            }
            // W
            if(k.second.second > 0 && !fixed[k.second.first][k.second.second-1] 
            && distances[k.second.first][k.second.second-1] > distances[k.second.first][k.second.second] + 2){
                cache.erase({distances[k.second.first][k.second.second-1], {k.second.first, k.second.second-1}});
                distances[k.second.first][k.second.second-1] = distances[k.second.first][k.second.second] + 2;
                cache.insert({distances[k.second.first][k.second.second-1], {k.second.first, k.second.second-1}});
            }
            // N
            if(k.second.first > 0 && !fixed[k.second.first-1][k.second.second] 
            && distances[k.second.first-1][k.second.second] > distances[k.second.first][k.second.second] + 3){
                cache.erase({distances[k.second.first-1][k.second.second], {k.second.first-1, k.second.second}});
                distances[k.second.first-1][k.second.second] = distances[k.second.first][k.second.second] + 3;
                cache.insert({distances[k.second.first-1][k.second.second], {k.second.first-1, k.second.second}});
            }
            continue;
        }

        // S
        if(board[k.second.first][k.second.second] == 'S') {
            fixed[k.second.first][k.second.second] = 1;
            if(k.second.second < n-1 && !fixed[k.second.first][k.second.second+1] 
            && distances[k.second.first][k.second.second+1] > distances[k.second.first][k.second.second] + 3){
                cache.erase({distances[k.second.first][k.second.second+1], {k.second.first, k.second.second+1}});
                distances[k.second.first][k.second.second+1] = distances[k.second.first][k.second.second] + 3;
                cache.insert({distances[k.second.first][k.second.second+1], {k.second.first, k.second.second+1}});
            }
            // S
            if(k.second.first < m-1 && !fixed[k.second.first+1][k.second.second] 
            && distances[k.second.first+1][k.second.second] > distances[k.second.first][k.second.second] + 0){
                cache.erase({distances[k.second.first+1][k.second.second], {k.second.first+1, k.second.second}});
                distances[k.second.first+1][k.second.second] = distances[k.second.first][k.second.second] + 0;
                cache.insert({distances[k.second.first+1][k.second.second], {k.second.first+1, k.second.second}});
            }
            // W
            if(k.second.second > 0 && !fixed[k.second.first][k.second.second-1] 
            && distances[k.second.first][k.second.second-1] > distances[k.second.first][k.second.second] + 1){
                cache.erase({distances[k.second.first][k.second.second-1], {k.second.first, k.second.second-1}});
                distances[k.second.first][k.second.second-1] = distances[k.second.first][k.second.second] + 1;
                cache.insert({distances[k.second.first][k.second.second-1], {k.second.first, k.second.second-1}});
            }
            // N
            if(k.second.first > 0 && !fixed[k.second.first-1][k.second.second] 
            && distances[k.second.first-1][k.second.second] > distances[k.second.first][k.second.second] + 2){
                cache.erase({distances[k.second.first-1][k.second.second], {k.second.first-1, k.second.second}});
                distances[k.second.first-1][k.second.second] = distances[k.second.first][k.second.second] + 2;
                cache.insert({distances[k.second.first-1][k.second.second], {k.second.first-1, k.second.second}});
            }
            continue;
        }

        // W
        if(board[k.second.first][k.second.second] == 'W') {
            fixed[k.second.first][k.second.second] = 1;
            if(k.second.second < n-1 && !fixed[k.second.first][k.second.second+1] 
            && distances[k.second.first][k.second.second+1] > distances[k.second.first][k.second.second] + 2){
                cache.erase({distances[k.second.first][k.second.second+1], {k.second.first, k.second.second+1}});
                distances[k.second.first][k.second.second+1] = distances[k.second.first][k.second.second] + 2;
                cache.insert({distances[k.second.first][k.second.second+1], {k.second.first, k.second.second+1}});
            }
            // S
            if(k.second.first < m-1 && !fixed[k.second.first+1][k.second.second] 
            && distances[k.second.first+1][k.second.second] > distances[k.second.first][k.second.second] + 3){
                cache.erase({distances[k.second.first+1][k.second.second], {k.second.first+1, k.second.second}});
                distances[k.second.first+1][k.second.second] = distances[k.second.first][k.second.second] + 3;
                cache.insert({distances[k.second.first+1][k.second.second], {k.second.first+1, k.second.second}});
            }
            // W
            if(k.second.second > 0 && !fixed[k.second.first][k.second.second-1] 
            && distances[k.second.first][k.second.second-1] > distances[k.second.first][k.second.second] + 0){
                cache.erase({distances[k.second.first][k.second.second-1], {k.second.first, k.second.second-1}});
                distances[k.second.first][k.second.second-1] = distances[k.second.first][k.second.second] + 0;
                cache.insert({distances[k.second.first][k.second.second-1], {k.second.first, k.second.second-1}});
            }
            // N
            if(k.second.first > 0 && !fixed[k.second.first-1][k.second.second] 
            && distances[k.second.first-1][k.second.second] > distances[k.second.first][k.second.second] + 1){
                cache.erase({distances[k.second.first-1][k.second.second], {k.second.first-1, k.second.second}});
                distances[k.second.first-1][k.second.second] = distances[k.second.first][k.second.second] + 1;
                cache.insert({distances[k.second.first-1][k.second.second], {k.second.first-1, k.second.second}});
            }
            continue;
        }

        // N
        if(board[k.second.first][k.second.second] == 'N') {
            fixed[k.second.first][k.second.second] = 1;
            if(k.second.second < n-1 && !fixed[k.second.first][k.second.second+1] 
            && distances[k.second.first][k.second.second+1] > distances[k.second.first][k.second.second] + 1){
                cache.erase({distances[k.second.first][k.second.second+1], {k.second.first, k.second.second+1}});
                distances[k.second.first][k.second.second+1] = distances[k.second.first][k.second.second] + 1;
                cache.insert({distances[k.second.first][k.second.second+1], {k.second.first, k.second.second+1}});
            }
            // S
            if(k.second.first < m-1 && !fixed[k.second.first+1][k.second.second] 
            && distances[k.second.first+1][k.second.second] > distances[k.second.first][k.second.second] + 2){
                cache.erase({distances[k.second.first+1][k.second.second], {k.second.first+1, k.second.second}});
                distances[k.second.first+1][k.second.second] = distances[k.second.first][k.second.second] + 2;
                cache.insert({distances[k.second.first+1][k.second.second], {k.second.first+1, k.second.second}});
            }
            // W
            if(k.second.second > 0 && !fixed[k.second.first][k.second.second-1] 
            && distances[k.second.first][k.second.second-1] > distances[k.second.first][k.second.second] + 3){
                cache.erase({distances[k.second.first][k.second.second-1], {k.second.first, k.second.second-1}});
                distances[k.second.first][k.second.second-1] = distances[k.second.first][k.second.second] + 3;
                cache.insert({distances[k.second.first][k.second.second-1], {k.second.first, k.second.second-1}});
            }
            // N
            if(k.second.first > 0 && !fixed[k.second.first-1][k.second.second] 
            && distances[k.second.first-1][k.second.second] > distances[k.second.first][k.second.second] + 0){
                cache.erase({distances[k.second.first-1][k.second.second], {k.second.first-1, k.second.second}});
                distances[k.second.first-1][k.second.second] = distances[k.second.first][k.second.second] + 0;
                cache.insert({distances[k.second.first-1][k.second.second], {k.second.first-1, k.second.second}});
            }
            continue;
        }
    }

    cout << (distances[m-1][n-1] == INF ? -1 : distances[m-1][n-1]) << '\n';
    
}

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