oj.uz

Submission #509806

# Submission time Handle Problem Language Result Execution time Memory
509806 2022-01-14T10:17:53 Z tudor Awesome Arrowland Adventure (eJOI19_adventure) C++17
12 / 100
 1 ms 332 KB 
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int nmax = 500;
const int dir = 4;
const int inf = 1e9;
int n, m;
char a[nmax + 2][nmax + 2];
int dl[dir] = { -1, 0, 1,  0 };
int dc[dir] = {  0, 1, 0, -1 };
int cod[128];
int dist[nmax * nmax + 1];
int vis[nmax * nmax + 1];
vector < pair < int, int > > g[nmax + 1];
void dijkstra ( int start ) {
    priority_queue < pair < int, int > > pq;
    for ( int i = 0; i < n * m; i++ ) {
        dist[i] = inf;
        vis[i] = false;
    }
    dist[0] = 0;
    pq.push ( { 0, start } );
    while ( ! pq.empty() ) {
        int node = pq.top ().second;
        pq.pop ();
        if ( vis[node] == false ) {
            vis[node] = true;
            for ( auto x: g[node] )
                if ( dist[node] + x.second < dist[x.first] ) {
                    dist[x.first] = dist[node] + x.second;
                    pq.push ( { -dist[x.first], x.first } );
                }
        }
    }
}
static inline void add ( int x, int y, int d ) {
    if ( 0 <= x && x < n * m && 0 <= y && y < n * m )
        g[x].push_back ( { y, d } );
}
static inline int lin ( int x, int y ) {
    if ( x < 0 || x >= n || y < 0 || y >= m )
        return -1;
    return x * m + y;
}
int vec[4];
int main () {
    cin >> n >> m;
    for ( int i = 0; i < n; i++ )
        cin >> a[i];
    cod['N'] = 0;
    cod['E'] = 1;
    cod['S'] = 2;
    cod['W'] = 3;
    for ( int i = 0; i < n; i++ )
        for ( int j = 0; j < n; j++ )
            if ( a[i][j] != 'X' ) {
                int curr = lin ( i, j ), x;
                for ( int d = 0; d < dir; d++ )
                    vec[d] = lin ( i + dl[d], j + dc[d] );
                for ( int k = 0; k < 4; k++ )
                    if ( ( x = vec[( cod[a[i][j]] + k ) % dir] ) != -1 )
                        add ( curr, x , k );
            }
    dijkstra ( 0 );
    int r = dist[lin ( n - 1, m - 1 )];
    cout << ( r == inf? -1 : r );
    
    return 0;
}

Compilation message

adventure.cpp: In function 'int main()':
adventure.cpp:62:48: warning: array subscript has type 'char' [-Wchar-subscripts]
   62 |                     if ( ( x = vec[( cod[a[i][j]] + k ) % dir] ) != -1 )
      |                                          ~~~~~~^

Subtask #1
0 / 10.0

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

Subtask #2
0 / 12.0

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

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct

Subtask #4
0 / 16.0

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

Subtask #5
0 / 50.0

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