Submission #1254340

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254340		warrenn	Awesome Arrowland Adventure (eJOI19_adventure)	C++20	100 / 100	70 ms	8880 KiB

adventure

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

int dx(char apa,int op){
    if(apa=='N'){
        if(op%2==0)return 0;
        if(op==1)return 1;
        return -1;
    }
    else if(apa=='E'){
        if(op==0)return 1;
        if(op==2)return -1;
        return 0;
    }
    else if(apa=='S'){
        if(op%2==0)return 0;
        if(op==1)return -1;
        return 1;
    }
    else{
        if(op==0)return -1;
        if(op==2)return 1;
        return 0;
    }
}

int dy(char apa,int op){
    if(apa=='W'){
        if(op%2==0)return 0;
        if(op==1)return -1;
        return 1;
    }
    else if(apa=='N'){
        if(op==0)return -1;
        if(op==2)return 1;
        return 0;
    }
    else if(apa=='E'){
        if(op%2==0)return 0;
        if(op==1)return 1;
        return -1;
    }
    else{
        if(op==0)return 1;
        if(op==2)return -1;
        return 0;
    }
}

int n,m;
bool ins(int x,int y){
    return (x>0 && y>0 && x<=n && y<=m);
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    char grid[n+1][m+1];
    int dist[n+1][m+1];
    for(int q=1;q<=n;q++){
        for(int w=1;w<=m;w++){
            cin>>grid[q][w];
            dist[q][w]=1e15;
        }
    }
    dist[1][1]=0;
    priority_queue<tuple<int,int,int>,vector<tuple<int,int,int> >,greater<tuple<int,int,int> > >pq;
    pq.push({0,1,1});

    while(pq.size()){
        auto [jrk,x,y]=pq.top();
        pq.pop();
        if(dist[x][y]!=jrk || grid[x][y]=='X')continue;
        for(int q=0;q<4;q++){
            int nx=x+dy(grid[x][y],q);
            int ny=y+dx(grid[x][y],q);
            if(ins(nx,ny)==false)continue;
            if(dist[nx][ny]>dist[x][y]+q){
                dist[nx][ny]=dist[x][y]+q;
                pq.push({dist[nx][ny],nx,ny});
            }
        }
    }
    if(dist[n][m]==1e15){
        cout<<-1<<endl;
    }
    else{
        cout<<dist[n][m]<<endl;
    }
}

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