Submission #1175814

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175814		tschav_	Awesome Arrowland Adventure (eJOI19_adventure)	C++20	100 / 100	67 ms	8956 KiB

adventure

#include <bits/stdc++.h>
#define int long long
using namespace std;
int T, n, m;
void solve() {
  cin >> n >> m;
  vector<vector<char>> v(n, vector<char>(m));
  for(auto &i : v) {
    for(auto &j : i) {
      cin >> j;
    }
  }
  vector<vector<int>> dist(n, vector<int>(m));
  for(auto &i : dist) {
    for(auto &j : i) {
      j = (int)1e18;
    }
  }
  dist[0][0] = 0;
  auto dir = [&](char from, int to) -> int {
    if(from == 'E') {
      array<int, 4> a = {0, 1, 2, 3};
      return a[to];
    } else if(from == 'S') {
      array<int, 4> a = {3, 0, 1, 2};
      return a[to];
    } else if(from == 'W') {
      array<int, 4> a = {2, 3, 0, 1};
      return a[to];
    } else {
      array<int, 4> a = {1, 2, 3, 0};
      return a[to];
    }
  };
  array<int, 4> dx = {0, 1, 0, -1};
  array<int, 4> dy = {1, 0, -1, 0};
  priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> q;
  q.push({0, {0, 0}});
  while(!q.empty()) {
    pair<int, pair<int, int>> t = q.top();
    q.pop();
    for(int i = 0; i < 4; i++) {
      int nx = t.second.first + dx[i];
      int ny = t.second.second + dy[i];
      auto [x, y] = t.second;
      if(v[x][y] == 'X') break;
      if(nx < 0 or nx > n-1 or ny < 0 or ny > m-1) continue;
      if(dist[nx][ny] > dist[x][y] + dir(v[x][y], i)) {
        dist[nx][ny] = dist[x][y] + dir(v[x][y], i);
        q.push({dist[nx][ny], {nx, ny}});
      }
    }
  }
  cout << (dist[n-1][m-1] == (int)1e18 ? -1 : dist[n-1][m-1]);
}
signed main() {
  cin.tie(0)->sync_with_stdio(0);
  T = 1;
  // cin >> T;
  while (T--) {
    solve();
  }
}

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 16 / 16
• Subtask 5: 50 / 50