제출 #543654

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
543654		tudor	Awesome Arrowland Adventure (eJOI19_adventure)	C++17	34 / 100	1 ms	340 KiB

adventure

#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;
    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;
    cod['X'] = -1;
    for ( int i = 0; i < n; i++ )
        for ( int j = 0; j < m; 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;
}

컴파일 시 표준 에러 (stderr) 메시지

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

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