oj.uz

Submission #371094

# Submission time Handle Problem Language Result Execution time Memory
371094 2021-02-25T19:56:46 Z kris01 Awesome Arrowland Adventure (eJOI19_adventure) C++14
0 / 100
 2000 ms 364 KB 
#include <bits/stdc++.h>
using namespace std;
#define pii pair <int,long long int>
#define mp make_pair
vector < vector <pii> > Adj;
vector <long long int> Dist;
long long int INF = LLONG_MAX;

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;

int convert(int a,int b) {
  return (a-1)*(m)+b;
}

int calc(char a,char b) {
  vector <char> V = {'N','E','S','W'};
  int idx;
  if (a == 'N') idx = 0;
  if (a == 'E') idx = 1;
  if (a == 'S') idx = 2;
  if (a == 'W') idx = 3;
  int res = 0;
  while (b != V[idx]) {
    res++;
    idx = (idx+1)% 4;
  }
  return res;
}

int main() {
	ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cin >> n >> m;
  vector < vector <char> > M(n+1,vector <char> (m+1,0));
  long long int val = (n+1)*(m+1);
  Adj.resize(val);
  Dist.resize(val,INF);
  for (int i = 1;i <= n;i++) {
    for (int j = 1;j <= m;j++) {
      cin >> M[i][j];
    }
  }
  for (int i = 1;i <= n;i++) {
    for (int j = 1;j <= m;j++) {
      if (i > 1) {
        int nxt = convert(i-1,j);
        int dist = calc(M[i][j],M[i-1][j]);
        Adj[convert(i,j)].push_back(mp(nxt,dist));
      }
      if (i < n) {
        int nxt = convert(i+1,j);
        int dist = calc(M[i][j],M[i+1][j]);
        Adj[convert(i,j)].push_back(mp(nxt,dist));
      }
      if (j > 1) {
        int nxt = convert(i,j-1);
        int dist = calc(M[i][j],M[i][j-1]);
        Adj[convert(i,j)].push_back(mp(nxt,dist));
      }
      if (j < m) {
        int nxt = convert(i,j+1);
        int dist = calc(M[i][j],M[i][j+1]);
        Adj[convert(i,j)].push_back(mp(nxt,dist));
      }
    }
  }
  Dijkstra(convert(1,1));
  cout << Dist[convert(n,m)]; 
	return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2062 ms 364 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2062 ms 364 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2074 ms 364 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2070 ms 364 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 50.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2062 ms 364 KB Time limit exceeded
2 Halted 0 ms 0 KB -