oj.uz

답안 #373480

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
373480 2021-03-04T19:22:05 Z kris01 Awesome Arrowland Adventure (eJOI19_adventure) C++14
0 / 100
 1 ms 492 KB 
#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+2)+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));  
  cout << Dist[vertex(n,m)];
	return 0;
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Incorrect 1 ms 364 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -