Submission #565897

#	Time	Username	Problem	Language	Result	Execution time	Memory
565897		mircea_007	Awesome Arrowland Adventure (eJOI19_adventure)	C++17	100 / 100	44 ms	4796 KiB

adventure

// This program was written on 21.05.2022
// for problem adventure
// by Mircea Rebengiuc

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

#define MAXN 500
#define MAXCH 128
#define INF 2000000000

int ch2type[MAXCH];

char inmat[1 + MAXN + 1][1 + MAXN + 1];

int initdir[MAXN][MAXN];
int dist[MAXN][MAXN];

int dl[4] = { -1, 0, 1, 0 };
int dc[4] = { 0, 1, 0, -1 };

std::priority_queue<std::pair<int, int>> heap;

int main(){
  int n, m, node, l, c, d, cand, final;
  
  ch2type[(int)'N'] = 0;
  ch2type[(int)'E'] = 1;
  ch2type[(int)'S'] = 2;
  ch2type[(int)'W'] = 3;
  ch2type[(int)'X'] = -1;
  
  scanf( "%d%d ", &n, &m );
  
  for( l = 0 ; l < n ; l++ ){
    for( c = 0 ; c < m ; c++ )
      initdir[l][c] = ch2type[(int)fgetc( stdin )];
    fgetc( stdin );// trecem peste '\n'
  }
  
  for( l = 0 ; l < n ; l++ )
    for( c = 0 ; c < m ; c++ ){
      dist[l][c] = +INF;
      inmat[l + 1][c + 1] = 1;
    }
  
  dist[0][0] = 0;
  heap.push( std::make_pair( 0, 0 ) );
  
  final = n * m - 1;

  while( !heap.empty() && (node = heap.top().second) != final ){
    heap.pop();
    
    l = node / m;
    c = node % m;
    
    if( initdir[l][c] >= 0 ){
      for( d = 0 ; d < 4 ; d++ ){
        if( inmat[l + 1 + dl[d]][c + 1 + dc[d]] ){
          cand = dist[l][c] + ((d + 4 - initdir[l][c]) & 3);
          if( cand < dist[l + dl[d]][c + dc[d]] ){
            dist[l + dl[d]][c + dc[d]] = cand;
            heap.push( std::make_pair( -cand, node + dc[d] + m * dl[d] ) );
          }
        }
      }
    }
  }
  
  printf( "%d\n", dist[n - 1][m - 1] == +INF ? -1 : dist[n - 1][m - 1] );

  return 0;
}

Compilation message (stderr)

adventure.cpp: In function 'int main()':
adventure.cpp:33:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |   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