Submission #999772

#	Time	Username	Problem	Language	Result	Execution time	Memory
999772		vjudge1	Awesome Arrowland Adventure (eJOI19_adventure)	C++14	34 / 100	53 ms	11940 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 =8*1e5 + 10, inf = 1e9, prime = 4567896467;

int cost[500][500];
char arr[500][500];
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 n,m;
vector<char> yonler;
int used[500][500];
void dfs(int x,int y,int c=0){
    used[x][y]++;
    if(x==n-1 && y==m-1){
        if(cost[x][y]==-1){
            cost[x][y]=inf;
        }
        cost[x][y]=min(cost[x][y],c);

        return;
    }
    if(arr[x][y]=='X' || (x>=n || y>=m || x<0 || y<0 || used[x][y]>10000 )|| ( cost[x][y]!=-1 && c>cost[x][y])){
        return;
    }
    // cout<<x<<" "<<y<<endl;
    if(cost[x][y]==-1){
        cost[x][y]=inf;
    }
    cost[x][y]=min(cost[x][y],c);
    
    for(auto v:yonler){
        if(v=='N'){
            dfs(x-1,y,c + cc(arr[x][y],v));
        }
        else if(v=='E'){
            dfs(x,y+1,c + cc(arr[x][y],v));
        }
        else if(v=='S'){
            dfs(x+1,y,c + cc(arr[x][y],v));
        }
        else if(v=='W'){
            dfs(x,y-1,c + cc(arr[x][y],v));
        }
    }
    // WNES
}
void mal(){
    cin>>n>>m;
    yonler={'N','E','S','W'};
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>arr[i][j];
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cost[i][j]=-1;
        }
    }
    cost[0][0]=0;
    cost[n-1][m-1]=-1;

    yc['N']=0;
    yc['E']=1;
    yc['S']=2;
    yc['W']=3;

    if(m==2){
        if(arr[0][0]=='X'){
            drop(-1);
        }
        cost[0][1] = cc(arr[0][0],'E');
        // cout<<cost[0][0]<<" "<<cost[0][1]<<endl;
        for(int i=1;i<n;i++){
            
            if(arr[i][0]!='X' || (0==m-1 && i==n-1)){
                if(cost[i-1][0]!=-1){
                    cost[i][0] = cost[i-1][0] + cc(arr[i-1][0],'S');    
                    // cout<<"sa:"<<i<<" " <<cost[i][0]<<endl;
                }
                if(cost[i-1][1]!=-1 && arr[i][1]!='X'){
                    if(cost[i][0]==-1){
                        cost[i][0]=inf;
                    }
                    cost[i][0]= min(cost[i][0], cost[i-1][1] + cc(arr[i-1][1],'S') + cc(arr[i][1],'W'));
                }
            }
            if(arr[i][1]!='X' || (1==m-1 && i==n-1)){
                // cout<<i<<" "<<1<<endl;
                if(cost[i-1][1]!=-1){
                    cost[i][1] = cost[i-1][1] + cc(arr[i-1][1],'S');    
                }

                if(cost[i-1][0]!=-1 && arr[i][0]!='X'){
                    if(cost[i][1]==-1){
                        cost[i][1]=inf;
                    }
                    cost[i][1]=min(cost[i][1],cost[i-1][0] + cc(arr[i-1][0],'S') + cc(arr[i][0],'E'));
                }
            }
            // cout<<i<<" "<<cost[i][0]<<" "<<cost[i][1]<<endl;
        
        }



        drop(cost[n-1][m-1]);
        return;
    }
    dfs(0,0);
    drop(cost[n-1][m-1]);
}

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:49:11: warning: array subscript has type 'char' [-Wchar-subscripts]
   49 |     if(yc[a]<=yc[b]){
      |           ^
adventure.cpp:49:18: warning: array subscript has type 'char' [-Wchar-subscripts]
   49 |     if(yc[a]<=yc[b]){
      |                  ^
adventure.cpp:50:19: warning: array subscript has type 'char' [-Wchar-subscripts]
   50 |         return yc[b]-yc[a];
      |                   ^
adventure.cpp:50:25: warning: array subscript has type 'char' [-Wchar-subscripts]
   50 |         return yc[b]-yc[a];
      |                         ^
adventure.cpp:52:19: warning: array subscript has type 'char' [-Wchar-subscripts]
   52 |     return 4 - yc[a] + yc[b];
      |                   ^
adventure.cpp:52:27: warning: array subscript has type 'char' [-Wchar-subscripts]
   52 |     return 4 - yc[a] + yc[b];
      |                           ^

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