oj.uz

Submission #287539

# Submission time Handle Problem Language Result Execution time Memory
287539 2020-08-31T19:32:03 Z eagle30 Awesome Arrowland Adventure (eJOI19_adventure) C++14
0 / 100
 1 ms 768 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Incorrect 0 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 768 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -