제출 #841603

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
841603		WLZ	Awesome Arrowland Adventure (eJOI19_adventure)	C++17	100 / 100	72 ms	21792 KiB

adventure

#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;

const vector<int> dx = {-1, 0, 1, 0};
const vector<int> dy = {0, 1, 0, -1};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  map<char, int> mp;
  mp['N'] = 0;
  mp['E'] = 1;
  mp['S'] = 2;
  mp['W'] = 3;
  int m, n;
  cin >> m >> n;
  auto idx = [n](int i, int j) {
    return i * n + j;
  };
  vector<string> grid(m);
  for (int i = 0; i < m; i++) {
    cin >> grid[i];
  }
  vector< vector< pair<int, int> > > g(m * n);
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
      if (grid[i][j] == 'X') {
        continue;
      }
      int cur = mp[grid[i][j]];
      int tmp = idx(i, j);
      for (int k = 0; k < 4; k++) {
        int ni = i + dx[cur];
        int nj = j + dy[cur];
        cur++;
        if (cur == 4) {
          cur = 0;
        }
        if (ni < 0 || ni >= m || nj < 0 || nj >= n) {
          continue;
        }
        g[tmp].push_back({idx(ni, nj), k});
      }
    }
  }
  vector<int> dist(m * n, INF);
  dist[0] = 0;
  priority_queue< pair<int, int>, vector< pair<int, int> >, greater< pair<int, int> > > pq;
  pq.push({0, 0});
  while (!pq.empty()) {
    int u = pq.top().second;
    int d = pq.top().first;
    pq.pop();
    if (d > dist[u]) {
      continue;
    }
    for (auto& v : g[u]) {
      if (d + v.second < dist[v.first]) {
        dist[v.first] = d + v.second;
        pq.push({dist[v.first], v.first});
      }
    }
  }
  if (dist[m * n - 1] == INF) {
    cout << -1 << '\n';
    return 0;
  }
  cout << dist[m * n - 1] << '\n';
  return 0;
}

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