제출 #399040

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
399040		Valaki2	Awesome Arrowland Adventure (eJOI19_adventure)	C++14	100 / 100	121 ms	26432 KiB

adventure

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

int n, m, val;
vector<vector<vector<pair<pair<int, int>, int> > > > g(502, vector<vector<pair<pair<int, int>, int> > > (502));
char ch;
bool done[502][502];
int dis[502][502];

struct node {
  int x, y;
  int dist;
  bool operator <(const node& other) const {
    return dist > other.dist;
  }
};

node n1, n2;

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
	cin >> n >> m;
  for(int i = 1; i <= n; ++i) {
    for(int j = 1; j <= m; ++j) {
      cin >> ch;
      if(ch == 'X') continue;
      if(ch == 'N') val = 0;
      if(ch == 'E') val = 1;
      if(ch == 'S') val = 2;
      if(ch == 'W') val = 3;
      g[i][j].push_back(make_pair(make_pair(i-1, j), (-val+4+0)%4));
      g[i][j].push_back(make_pair(make_pair(i, j+1), (-val+4+1)%4));
      g[i][j].push_back(make_pair(make_pair(i+1, j), (-val+4+2)%4));
      g[i][j].push_back(make_pair(make_pair(i, j-1), (-val+4+3)%4));
      /*for(auto p : g[i][j]) {
        cout << i << " " << j << " -> " << p.first.first << " " << p.first.second << ": " << p.second << "\n";
      }*/
    }
  }
  for(int i = 0; i <= n+1; ++i) {
    for(int j = 0; j <= m+1; ++j) {
      dis[i][j] = -1;
    }
  }
  priority_queue<node> q;
  n1.x = 1;
  n1.y = 1;
  n1.dist = 0;
  dis[n1.x][n1.y] = 0;
  q.push(n1);
  while(!q.empty()) {
    n1 = q.top();
    q.pop();
    if(!done[n1.x][n1.y]) {
      done[n1.x][n1.y] = true;
      for(auto u : g[n1.x][n1.y]) {
        if(!done[u.first.first][u.first.second]) {
          if((dis[u.first.first][u.first.second] == -1) || (dis[u.first.first][u.first.second] > dis[n1.x][n1.y]+u.second)) {
            n2.x = u.first.first;
            n2.y = u.first.second;
            n2.dist = dis[n1.x][n1.y] + u.second;
            dis[n2.x][n2.y] = n2.dist;
            q.push(n2);
          }
        }
      }
    }
  }
  cout << dis[n][m] << "\n";
	return 0;
}

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