Submission #1222813

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222813		Solikha	Awesome Arrowland Adventure (eJOI19_adventure)	C++20	100 / 100	66 ms	11096 KiB

adventure

#include "bits/stdc++.h"
using namespace std;
#define int long long
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define ss second
#define ff first
#define pb push_back 
using ull = unsigned long long;
typedef pair<int, tuple<int, int, char>> Node;
 
void solve(){
  int n, m; cin >> n >> m;
  vector<string> v(n);
  for(int i = 0; i < n; i++) cin >> v[i];
  vector<vector<int>> dis(n, vector<int> (m, 1e18));
  priority_queue<Node, vector<Node>, greater<Node>> pq;
  vector<int> dx = {1, -1, 0, 0};
  vector<int> dy = {0, 0, 1, -1};
  if(v[0][0] == 'X'){
    cout << -1; return;
  }
  dis[0][0] = 0;
  pq.push({0, {0, 0, v[0][0]}});
  while(!pq.empty()){
    auto [cost, dir] = pq.top();
    pq.pop();
    auto [x, y, ch] = dir;

    if(cost > dis[x][y]) continue;

    for(int k = 0; k < 4; k++){
      int i = x + dx[k];
      int j = y + dy[k];
      if(i < 0 || i >= n || j < 0 || j >= m) continue;
      if(v[i][j] == 'X'){
        if(i == n - 1 && j == m - 1);
        else continue;
      }
      int nwc = cost;
      if(ch == 'W'){
        if(dx[k] == 1) nwc += 3;
        if(dx[k] == -1) nwc ++;
        if(dy[k] == 1) nwc += 2;
      }else if(ch == 'S'){
        if(dx[k] == -1) nwc += 2;
        if(dy[k] == 1) nwc += 3;
        if(dy[k] == -1) nwc ++;
      }else if(ch == 'E'){
        if(dx[k] == 1) nwc ++;
        if(dx[k] == -1) nwc += 3;
        if(dy[k] == -1) nwc += 2;
      }else{
        if(dx[k] == 1) nwc += 2;
        if(dy[k] == 1) nwc ++;
        if(dy[k] == -1) nwc += 3;
      }
      //cerr << nwc << ' ' << i << ' ' << j << ' ' << v[i][j] << endl;
      if(nwc < dis[i][j]){
        dis[i][j] = nwc;
        pq.push({nwc, {i, j, v[i][j]}});
      }
    }
  }
  if(dis[n - 1][m - 1] >=  1e18) cout << -1;
  else cout << dis[n - 1][m - 1];
}

signed main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int t = 1; //cin >> t;
  while(t--){
    solve();
    //cout << endl;
  }

  return 0;
}

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