oj.uz

Submission #459209

# Submission time Handle Problem Language Result Execution time Memory
459209 2021-08-08T10:38:14 Z RaresFelix Awesome Arrowland Adventure (eJOI19_adventure) C++17
0 / 100
 1 ms 204 KB 
#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 = max(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
0 / 10.0

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

Subtask #2
0 / 12.0

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

Subtask #3
0 / 12.0

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

Subtask #4
0 / 16.0

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

Subtask #5
0 / 50.0

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