oj.uz

Submission #565897

# Submission time Handle Problem Language Result Execution time Memory
565897 2022-05-21T13:52:42 Z mircea_007 Awesome Arrowland Adventure (eJOI19_adventure) C++17
100 / 100
 44 ms 4796 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];

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

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.0 / 10.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 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 300 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 296 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct

Subtask #2
12.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 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 300 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 296 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 296 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct

Subtask #3
12.0 / 12.0

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

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 300 KB Output is correct
5 Correct 0 ms 296 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 304 KB Output is correct
10 Correct 0 ms 212 KB Output is correct

Subtask #5
50.0 / 50.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 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 300 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 296 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 296 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 0 ms 212 KB Output is correct
24 Correct 0 ms 212 KB Output is correct
25 Correct 0 ms 212 KB Output is correct
26 Correct 1 ms 212 KB Output is correct
27 Correct 1 ms 212 KB Output is correct
28 Correct 0 ms 300 KB Output is correct
29 Correct 0 ms 296 KB Output is correct
30 Correct 0 ms 212 KB Output is correct
31 Correct 0 ms 212 KB Output is correct
32 Correct 0 ms 212 KB Output is correct
33 Correct 0 ms 304 KB Output is correct
34 Correct 0 ms 212 KB Output is correct
35 Correct 4 ms 468 KB Output is correct
36 Correct 0 ms 212 KB Output is correct
37 Correct 5 ms 800 KB Output is correct
38 Correct 1 ms 1464 KB Output is correct
39 Correct 44 ms 2756 KB Output is correct
40 Correct 43 ms 2744 KB Output is correct
41 Correct 3 ms 2644 KB Output is correct
42 Correct 44 ms 2756 KB Output is correct
43 Correct 44 ms 4796 KB Output is correct
44 Correct 3 ms 2644 KB Output is correct