제출 #459199

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
459199		RaresFelix	Awesome Arrowland Adventure (eJOI19_adventure)	C++17	12 / 100	1 ms	204 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 += dist(A[inainte.lin][inainte.col], (d+2)%4);
            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: 0 / 10
• Subtask 2: 0 / 12
• Subtask 3: 12 / 12
• Subtask 4: 0 / 16
• Subtask 5: 0 / 50