oj.uz

Submission #565720

# Submission time Handle Problem Language Result Execution time Memory
565720 2022-05-21T09:55:34 Z mircea_007 Awesome Arrowland Adventure (eJOI19_adventure) C++17
0 / 100
 2000 ms 264 KB 
// 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];

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;
  
  dist[0][0] = 0;
  heap.push( std::make_pair( 0, 0 ) );
  
  final = n * m - 1;

  while( (node = heap.top().second) != final ){
    heap.pop();
    
    l = node / m;
    c = node % m;
    
    if( initdir[l][c] >= 0 ){
      for( d = 0 ; d < 4 ; 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] );

  return 0;
}

Compilation message

adventure.cpp: In function 'int main()':
adventure.cpp:31:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |   scanf( "%d%d ", &n, &m );
      |   ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2075 ms 264 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2075 ms 264 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Execution timed out 2077 ms 212 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2080 ms 212 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 50.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2075 ms 264 KB Time limit exceeded
2 Halted 0 ms 0 KB -