Submission #287539

#	Time	Username	Problem	Language	Result	Execution time	Memory
287539		eagle30	Awesome Arrowland Adventure (eJOI19_adventure)	C++14	0 / 100	1 ms	768 KiB

adventure

#include<bits/stdc++.h>
using namespace std;
char arr[1000][1000];
long long n, m, memo[3][501][1501], is[3][501][1501];
int dist(char a, char b){
    if(a=='N'){
        if(b=='N')
            return 0;
        else if(b=='E')
            return 1;
        else if(b=='S')
            return 2;
        else
            return 3;
    }
    else if(a=='E'){
        if(b=='N')
            return 3;
        else if(b=='E')
            return 0;
        else if(b=='S')
            return 1;
        else
            return 2;
    }
    else if(a=='S'){
        if(b=='N')
            return 2;
        else if(b=='E')
            return 3;
        else if(b=='S')
            return 0;
        else
            return 1;
    }
    else{
        if(b=='N')
            return 1;
        else if(b=='E')
            return 2;
        else if(b=='S')
            return 3;
        else
            return 0;
    }
}
long long recursive(long long hi1, long long hi2, long long yo){
    if(hi1<0 || hi1>=n || hi2<0 || hi2>=m)
        return 1000000000;
    if(hi1==n-1 && hi2==m-1)
        return 0;
    if(arr[hi1][hi2]=='X' || yo==0)
        return 1000000000;
    if(is[hi1][hi2][yo])
        return memo[hi1][hi2][yo];
    long long mini=2e9;
    char asdf=arr[hi1][hi2];
    mini=min(mini, recursive(hi1+1, hi2, yo-1)+dist(asdf, 'S'));
    mini=min(mini, recursive(hi1-1, hi2, yo-1)+dist(asdf, 'N'));
    mini=min(mini, recursive(hi1, hi2+1, yo-1)+dist(asdf, 'E'));
    mini=min(mini, recursive(hi1, hi2-1, yo-1)+dist(asdf, 'W'));
    is[hi1][hi2][yo]=true;
    return memo[hi1][hi2][yo]=mini;
}
int main(){
cin>>n>>m;
for(long long i=0; i<n; i++){
    for(long long j=0; j<m; j++){
        cin>>arr[i][j];
    }
}
cout<<recursive(0, 0, n*m);
return 0;
}

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