oj.uz

Submission #528112

# Submission time Handle Problem Language Result Execution time Memory
528112 2022-02-19T09:46:06 Z nemethm Awesome Arrowland Adventure (eJOI19_adventure) C++17
22 / 100
 1 ms 332 KB 
#include <iostream>
#include <vector>
#include <deque>
#include <set>
#include <queue>
#include <string>
#include <limits>
#include <map>
#include <algorithm>
#include <stack>

using namespace std;
using ll = long long int;
const ll mod = 1e9 + 7;
int n, m;
int dist[510][510];
char g[510][510];
bool done[510][510] = {false};
map<char, pair<int,int>> dir = { {'E', {0,1}}, {'S', {1,0}}, {'W', {0,-1}}, {'N', {-1,0}} };
map<char, char> kov = { {'E', 'S'}, {'S', 'W'}, {'W', 'N'}, {'N', 'E'}};
vector<pair<int,pair<int,int>>> neighbour(pair<int,int> p){
  if(g[p.first][p.second] == 'X'){
    return {};
  }
  vector<pair<int,pair<int,int>>> v;
  char c = g[p.first][p.second];
  int cost = 0;
  do{
    pair<int,int> index = {p.first + dir[c].first, p.second + dir[c].second};
    if(index.first >= 0 && index.first < n && index.second >= 0 && index.second < m){
      v.push_back({cost, index});
    }
    ++cost;
    c = kov[c];
  }while(c != g[p.first][p.second]);
  return v;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> m;
  for(int i = 0; i < n; ++i){
    for(int j = 0; j < m; ++j){
      dist[i][j] = mod;
      cin >> g[i][j];
    }
  }
  dist[0][0] = 0;
  priority_queue<pair<int,pair<int,int>>> q;
  q.push({0,{0,0}});
  while(!q.empty()){
    auto s = q.top().second;
    q.pop();
    if(done[s.first][s.second]) continue;
    done[s.first][s.second] = true;
    vector<pair<int,pair<int,int>>> v = neighbour(s);
    for(auto i : v){
      auto coordinate = i.second;
      if(dist[coordinate.first][coordinate.second] > dist[s.first][s.second] + i.first){
        dist[coordinate.first][coordinate.second] = dist[s.first][s.second] + i.first;
        q.push({dist[coordinate.first][coordinate.second], coordinate});
      }
    }
  }
  if(dist[n - 1][m - 1] != mod)
    cout << dist[n - 1][m - 1] << endl;
  else
    cout << -1 << endl;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 0 ms 332 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 0 ms 204 KB Output is correct
17 Correct 0 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 0 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 0 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 0 ms 332 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 0 ms 204 KB Output is correct
17 Correct 0 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 0 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Incorrect 1 ms 332 KB Output isn't correct
22 Halted 0 ms 0 KB -