제출 #373481

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

adventure

#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pii pair<long long,long long>
vector < vector <pii> > Adj;
vector <long long int> Dist;
long long int INF = LLONG_MAX;
long long int LARGE = (long long)1e9;

void Dijkstra(int start) {
  Dist[start] = 0;
  priority_queue<pii,vector <pii>,greater <pii> > PQ;
  PQ.push(mp(0,start));
  while (!PQ.empty()) {
   int v = PQ.top().second;
   long long int d_v = PQ.top().first;
   PQ.pop();
   if (d_v != Dist[v]) continue;
   for (auto PR : Adj[v]) {
    if (Dist[PR.first] > Dist[v] + PR.second) {
      Dist[PR.first] = Dist[v] + PR.second;
      PQ.push(mp(Dist[PR.first],PR.first));
    }
   } 
  }
}

int n,m;

inline long long vertex(int a,int b) {
  return (a-1)*(m+1)+b;
}

int main() {
	ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cin >> n >> m;
  long long int val = (n+2)*(m+2)+5;
  Adj.resize(val);
  Dist.resize(val,INF);
  for (int i = 1;i <= n;i++) {
    for (int j = 1;j <= m;j++) {
      char c;
      cin >> c;
      if (c == 'W') {
        if (j != 1)  Adj[vertex(i,j)].push_back(mp(vertex(i,j-1),0));
        if (i != 1)  Adj[vertex(i,j)].push_back(mp(vertex(i-1,j),1));
        if (j != m)  Adj[vertex(i,j)].push_back(mp(vertex(i,j+1),2));
        if (i != n)  Adj[vertex(i,j)].push_back(mp(vertex(i+1,j),3));
      }
      if (c == 'E') {
        if (j != 1)  Adj[vertex(i,j)].push_back(mp(vertex(i,j-1),2));
        if (i != 1)  Adj[vertex(i,j)].push_back(mp(vertex(i-1,j),3));
        if (j != m)  Adj[vertex(i,j)].push_back(mp(vertex(i,j+1),0));
        if (i != n)  Adj[vertex(i,j)].push_back(mp(vertex(i+1,j),1)); 
      }
      if (c == 'N') {
        if (j != 1) Adj[vertex(i,j)].push_back(mp(vertex(i,j-1),3));
        if (i != 1) Adj[vertex(i,j)].push_back(mp(vertex(i-1,j),0));
        if (j != m) Adj[vertex(i,j)].push_back(mp(vertex(i,j+1),1));
        if (i != n) Adj[vertex(i,j)].push_back(mp(vertex(i+1,j),2));
      }
      if (c == 'S') {
       if (j != 1) Adj[vertex(i,j)].push_back(mp(vertex(i,j-1),1));
       if (i != 1) Adj[vertex(i,j)].push_back(mp(vertex(i-1,j),2));
       if (j != m) Adj[vertex(i,j)].push_back(mp(vertex(i,j+1),3));
       if (i != n) Adj[vertex(i,j)].push_back(mp(vertex(i+1,j),0));
      }
    }
  }  
  Dijkstra(vertex(1,1));  
  if (Dist[vertex(n,m)] == INF) {
    cout << -1;
    return 0;
  }
  cout << Dist[vertex(n,m)];
	return 0;
}

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