제출 #443014

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
443014		LucaIlie	Awesome Arrowland Adventure (eJOI19_adventure)	C++17	100 / 100	108 ms	22200 KiB

adventure

#include <stdio.h>
#include <queue>
#include <vector>
#include <ctype.h>

#define MAX_N 500
#define DIR 4

using namespace std;

struct muchie {
    int nod, cost;
    bool operator < (const muchie &aux) const {
        return cost > aux.cost;
    }
};

int dist[MAX_N * MAX_N], dir[MAX_N + 2][MAX_N + 2];
int dl[DIR] = { -1, 0, 1, 0 }, dc[DIR] = { 0, 1, 0, -1 };
vector <muchie> muchii[MAX_N * MAX_N];
priority_queue <muchie> pq;

char nextChar() {
    char ch;

    ch = getc( stdin );
    while ( !isalpha( ch ) )
        ch = getc( stdin );

    return ch;
}

int main() {
    char ch;
    int n, m, l, c, d, i;
    struct muchie crt, next;

    scanf( "%d%d", &n, &m );
    for ( l = 1; l <= n; l++ ) {
        for ( c = 1; c <= m; c++ ) {
            ch = nextChar();
            if ( ch == 'N' )
                dir[l][c] = 0;
            else if ( ch == 'E' )
                dir[l][c] = 1;
            else if ( ch == 'S' )
                dir[l][c] = 2;
            else if ( ch == 'W' )
                dir[l][c] = 3;
            else
                dir[l][c] = 4;
        }
    }

    for ( l = 1; l <= n; l++ )
        dir[l][0] = dir[l][m + 1] = -1;
    for ( c = 1; c <= m; c++ )
        dir[0][c] = dir[n + 1][c] = -1;


    for ( l = 1; l <= n; l++ ) {
        for ( c = 1; c <= m; c++ ) {
            if ( dir[l][c] < 4 ) {
                for ( d = 0; d < DIR; d++ ) {
                    if ( dir[l + dl[d]][c + dc[d]] >= 0 )
                        muchii[(l - 1) * m + c - 1].push_back( { (l - 1 + dl[d]) * m + c - 1 + dc[d], (d - dir[l][c] + DIR) % DIR } );
                }
            }
        }
    }

    for ( i = 0; i < n * m; i++ )
        dist[i] = -1;

    pq.push( { 0, 0 } );
    while ( !pq.empty() ) {
        crt = pq.top();
        pq.pop();
        if ( dist[crt.nod] == -1 ) {
            dist[crt.nod] = crt.cost;
            for ( i = 0; i < muchii[crt.nod].size(); i++ ) {
                next = muchii[crt.nod][i];
                if ( dist[next.nod] == -1 )
                    pq.push( { next.nod, dist[crt.nod] + next.cost } );
            }
        }
    }

    printf( "%d ", dist[n * m - 1] );

    return 0;
}

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

adventure.cpp: In function 'int main()':
adventure.cpp:81:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<muchie>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |             for ( i = 0; i < muchii[crt.nod].size(); i++ ) {
      |                          ~~^~~~~~~~~~~~~~~~~~~~~~~~
adventure.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |     scanf( "%d%d", &n, &m );
      |     ~~~~~^~~~~~~~~~~~~~~~~~

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