Submission #528111

#	Time	Username	Problem	Language	Result	Execution time	Memory
528111		nemethm	Awesome Arrowland Adventure (eJOI19_adventure)	C++17	50 / 100	2060 ms	636 KiB

adventure

#include <iostream>
#include <vector>
#include <deque>
#include <set>
#include <queue>
#include <string>
#include <limits>
#include <map>
#include <algorithm>
#include <stack>

using namespace std;
using ll = long long int;
const ll mod = 1e9 + 7;
int n, m;
int dist[510][510];
char g[510][510];
bool done[510][510] = {false};
map<char, pair<int,int>> dir = { {'E', {0,1}}, {'S', {1,0}}, {'W', {0,-1}}, {'N', {-1,0}} };
map<char, char> kov = { {'E', 'S'}, {'S', 'W'}, {'W', 'N'}, {'N', 'E'}};
vector<pair<int,pair<int,int>>> neighbour(pair<int,int> p){
  if(g[p.first][p.second] == 'X'){
    return {};
  }
  vector<pair<int,pair<int,int>>> v;
  char c = g[p.first][p.second];
  int cost = 0;
  do{
    pair<int,int> index = {p.first + dir[c].first, p.second + dir[c].second};
    if(index.first >= 0 && index.first < n && index.second >= 0 && index.second < m){
      v.push_back({cost, index});
    }
    ++cost;
    c = kov[c];
  }while(c != g[p.first][p.second]);
  return v;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> m;
  for(int i = 0; i < n; ++i){
    for(int j = 0; j < m; ++j){
      dist[i][j] = mod;
      cin >> g[i][j];
    }
  }
  dist[0][0] = 0;
  priority_queue<pair<int,pair<int,int>>> q;
  q.push({0,{0,0}});
  while(!q.empty()){
    auto s = q.top().second;
    q.pop();
    if(done[s.first][s.second]) continue;
    vector<pair<int,pair<int,int>>> v = neighbour(s);
    for(auto i : v){
      auto coordinate = i.second;
      if(dist[coordinate.first][coordinate.second] > dist[s.first][s.second] + i.first){
        dist[coordinate.first][coordinate.second] = dist[s.first][s.second] + i.first;
        q.push({dist[coordinate.first][coordinate.second], coordinate});
      }
    }
  }
  if(dist[n - 1][m - 1] != mod)
    cout << dist[n - 1][m - 1] << endl;
  else
    cout << -1 << endl;
}

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