Submission #459211

#	Time	Username	Problem	Language	Result	Execution time	Memory
459211		RaresFelix	Awesome Arrowland Adventure (eJOI19_adventure)	C++17	100 / 100	109 ms	5736 KiB

adventure

#include <bits/stdc++.h>
#define MN 571
#define INF 1000000000
using namespace std;
int n, m, A[MN][MN], D[MN][MN];
char C[MN];
struct poz {
    int lin, col, cost;
    bool operator<(const poz &b) const {
        return cost > b.cost;
    }
};
priority_queue<poz> BFQ;
int dist(int a, int b) {
    if(a==4 || b==4)return INF;
    return (b-a+4)%4;
}
int DX[] = {-1, 0, 1, 0};
int DY[] = {0, 1, 0, -1};
int main() {
    cin >> n >> m;
    for(int i = 1; i <= n; ++i){
        cin >> (C+1);
        for(int j = 1; j <= m; ++j)
            if(C[j] == 'N') A[i][j] = 0;
            else if(C[j] == 'E') A[i][j] = 1;
            else if(C[j] == 'S') A[i][j] = 2;
            else if(C[j] == 'W') A[i][j] = 3;
            else A[i][j] = 4;
    }
    D[n][m] = 1;
    BFQ.push({n, m, 1});
    poz acum, inainte;
    while(!BFQ.empty()){
        acum = BFQ.top();
        BFQ.pop();
        for(int d = 0; d < 4; ++d){
            inainte = {acum.lin + DX[d], acum.col + DY[d], acum.cost};
            inainte.cost = min(inainte.cost + dist(A[inainte.lin][inainte.col], (d+2)%4), INF);
            if((D[inainte.lin][inainte.col] && D[inainte.lin][inainte.col] <= inainte.cost) || inainte.lin < 1 || inainte.col < 1 || inainte.lin > n || inainte.col > m)
                continue;
            D[inainte.lin][inainte.col] = inainte.cost;
            BFQ.push(inainte);
        }
    }
    if(D[1][1] >= INF)
        D[1][1] = 0;
    cout << D[1][1] - 1;
    return 0;
}

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