Submission #999895

#	Time	Username	Problem	Language	Result	Execution time	Memory
999895		vjudge1	Awesome Arrowland Adventure (eJOI19_adventure)	C++14	100 / 100	81 ms	60752 KiB

adventure

/*       ==========================
        | Bismillahirrahmanirrahim | ⠀⠀ 
         ==========================
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠸⠁⠸⢳⡄⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⠃⠀⠀⢸⠸⠀⡠⣄⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡠⠃⠀⠀⢠⣞⣀⡿⠀⠀⣧⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣠⡖⠁⠀⠀⠀⢸⠈⢈⡇⠀⢀⡏⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⡴⠩⢠⡴⠀⠀⠀⠀⠀⠈⡶⠉⠀⠀⡸⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⢀⠎⢠⣇⠏⠀⠀⠀⠀⠀⠀⠀⠁⠀⢀⠄⡇⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⢠⠏⠀⢸⣿⣴⠀⠀⠀⠀⠀⠀⣆⣀⢾⢟⠴⡇⠀⠀⠀⠀⠀<===== this is wolf, not everest
⠀⠀⠀⠀⠀⢀⣿⠀⠠⣄⠸⢹⣦⠀⠀⡄⠀⠀⢋⡟⠀⠀⠁⣇⠀⠀⠀⠀⠀
⠀⠀⠀⠀⢀⡾⠁⢠⠀⣿⠃⠘⢹⣦⢠⣼⠀⠀⠉⠀⠀⠀⠀⢸⡀⠀⠀⠀⠀
⠀⠀⢀⣴⠫⠤⣶⣿⢀⡏⠀⠀⠘⢸⡟⠋⠀⠀⠀⠀⠀⠀⠀⠀⢳⠀⠀⠀⠀
⠐⠿⢿⣿⣤⣴⣿⣣⢾⡄⠀⠀⠀⠀⠳⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢣⠀⠀⠀
⠀⠀⠀⣨⣟⡍⠉⠚⠹⣇⡄⠀⠀⠀⠀⠀⠀⠀⠀⠈⢦⠀⠀⢀⡀⣾⡇⠀⠀
⠀⠀⢠⠟⣹⣧⠃⠀⠀⢿⢻⡀⢄⠀⠀⠀⠀⠐⣦⡀⣸⣆⠀⣾⣧⣯⢻⠀⠀
⠀⠀⠘⣰⣿⣿⡄⡆⠀⠀⠀⠳⣼⢦⡘⣄⠀⠀⡟⡷⠃⠘⢶⣿⡎⠻⣆⠀⠀
⠀⠀⠀⡟⡿⢿⡿⠀⠀⠀⠀⠀⠙⠀⠻⢯⢷⣼⠁⠁⠀⠀⠀⠙⢿⡄⡈⢆⠀
⠀⠀⠀⠀⡇⣿⡅⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⠦⠀⠀⠀⠀⠀⠀⡇⢹⢿⡀
⠀⠀⠀⠀⠁⠛⠓⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠼⠇⠁ 

m : 11059739 -> l ~23
p : 4567896467
*/
#pragma GCC optimize("O3", "inline")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define all(v) v.begin(), v.end()
#define ins insert
#define pb push_back
#define int long long int
#define pii pair<int, int>
#define str string
#define endl '\n'
#define drop(x) cout<<(x)<<endl;return;
// mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <class T> using ot = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const int mod = 998244353, sze =1e6 + 10, inf = 1e9, prime = 4567896467;



vector<pair<int,int>> graph[sze];
int dist[sze];
int yc[sze];

int cc(char a,char b){
    if(yc[a]<=yc[b]){
        return yc[b]-yc[a];
    }
    return 4 - yc[a] + yc[b];
}
int used[sze];
pii p[600][600];
void mal(){
    int n,m;
    cin>>n>>m;
    yc['N']=0;
    yc['E']=1;
    yc['S']=2;
    yc['W']=3;
    vector<char> yonler = {'N','E','S','W'};
    auto idx = [&](int a,int b){
        return a *m +b;
    };  
    for(int i=0;i<sze;i++){
        dist[i]=inf;
    }
    vector<vector<char>> arr(n,vector<char>(m));
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>arr[i][j];
        }
    }
    // cout<<cc('W','S')<<endl;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){

            if(arr[i][j]!='X'){

                for(auto v:yonler){
                    
                    int c = cc(arr[i][j],v);

                    int i1 = i;
                    int j1 = j;

                    if(v=='E'){
                        j1++;
                    }
                    else if(v=='S'){
                        i1++;
                    }
                    else if(v=='N'){
                        i1--;
                    }
                    else{
                        j1--;
                    }

                    if(i1>=0 && j1>=0 && i1<n && j1<m){
                        // cout<<i<<":"<<j<<" -> "<<i1<<":"<<j1<<" cost:"<<c<< " p-----p " <<v<<endl;
                        graph[idx(i,j)].pb( {  idx(i1,j1) , c });
                    }


                }
                
            }
        }
    }

    set<pair<int,int>> q;
    dist[idx(0,0)]=0;
    q.insert({0,idx(0,0)});
    p[0][0]={-1,-1};
    while(!q.empty()){
        pii node = *q.begin();
        q.erase(q.begin());

        for(auto v:graph[node.second]){

            if(dist[v.first] > dist[node.second] + v.second){
                q.erase({dist[v.first],v.first});
                dist[v.first]=dist[node.second]+v.second;
                p[v.first/m][v.first%m] = {node.second/m,node.second%m};
                // cout<<node.second/m<<":"<<node.second%m<<" ->"<< v.first/m<<":"<<v.first%m<<" c:"<<dist[v.first] << endl;
                q.insert({dist[v.first],v.first});
            }


        }
    }

    // cout<<p[n-1][m-1].first<<" "<<p[n-1][m-1].second<<endl;
    int ans=dist[idx(n-1,m-1)];
    if(ans>=inf){
        ans=-1;
    }
    drop(ans);

}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int tt = 1;
    // cin>>tt;

    while (tt--) mal();
}

Compilation message (stderr)

adventure.cpp: In function 'long long int cc(char, char)':
adventure.cpp:51:11: warning: array subscript has type 'char' [-Wchar-subscripts]
   51 |     if(yc[a]<=yc[b]){
      |           ^
adventure.cpp:51:18: warning: array subscript has type 'char' [-Wchar-subscripts]
   51 |     if(yc[a]<=yc[b]){
      |                  ^
adventure.cpp:52:19: warning: array subscript has type 'char' [-Wchar-subscripts]
   52 |         return yc[b]-yc[a];
      |                   ^
adventure.cpp:52:25: warning: array subscript has type 'char' [-Wchar-subscripts]
   52 |         return yc[b]-yc[a];
      |                         ^
adventure.cpp:54:19: warning: array subscript has type 'char' [-Wchar-subscripts]
   54 |     return 4 - yc[a] + yc[b];
      |                   ^
adventure.cpp:54:27: warning: array subscript has type 'char' [-Wchar-subscripts]
   54 |     return 4 - yc[a] + yc[b];
      |                           ^

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