oj.uz

답안 #528113

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
528113 2022-02-19T09:47:18 Z nemethm Awesome Arrowland Adventure (eJOI19_adventure) C++17
100 / 100
 113 ms 5060 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 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 332 KB Output is correct
10 Correct 0 ms 204 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 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 332 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 324 KB Output is correct
20 Correct 1 ms 204 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 204 KB Output is correct

Subtask #4
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 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 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 0 ms 332 KB Output is correct

Subtask #5
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 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 332 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 324 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 0 ms 332 KB Output is correct
22 Correct 0 ms 204 KB Output is correct
23 Correct 0 ms 332 KB Output is correct
24 Correct 0 ms 204 KB Output is correct
25 Correct 1 ms 332 KB Output is correct
26 Correct 0 ms 332 KB Output is correct
27 Correct 1 ms 204 KB Output is correct
28 Correct 0 ms 204 KB Output is correct
29 Correct 1 ms 204 KB Output is correct
30 Correct 1 ms 332 KB Output is correct
31 Correct 1 ms 332 KB Output is correct
32 Correct 1 ms 332 KB Output is correct
33 Correct 1 ms 332 KB Output is correct
34 Correct 0 ms 332 KB Output is correct
35 Correct 7 ms 460 KB Output is correct
36 Correct 1 ms 332 KB Output is correct
37 Correct 8 ms 548 KB Output is correct
38 Correct 1 ms 972 KB Output is correct
39 Correct 91 ms 2092 KB Output is correct
40 Correct 76 ms 2012 KB Output is correct
41 Correct 5 ms 1740 KB Output is correct
42 Correct 77 ms 2092 KB Output is correct
43 Correct 113 ms 5060 KB Output is correct
44 Correct 4 ms 1764 KB Output is correct