Submission #1161113

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161113		fryingduc	Awesome Arrowland Adventure (eJOI19_adventure)	C++20	100 / 100	26 ms	8772 KiB

adventure

#include "bits/stdc++.h"

using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 505;
int n, m;
char a[maxn][maxn];
int d[maxn][maxn][5];

int movex[] = {0, 1, 0, -1};
int movey[] = {1, 0, -1, 0};
char move_dir[] = {'E', 'S', 'W', 'N'};

int convert(char x) {
  for (int i = 0; i < 4; ++i) {
    if (x == move_dir[i]) {
      return i;
    }
  }
  return -1;
}

void solve() {
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      cin >> a[i][j];
    }
  }
  a[n][m] = 'S';
  deque<tuple<int, int, int>> dq;
  memset(d, 0x3f, sizeof(d));
  d[1][1][convert(a[1][1])] = 0;
  dq.push_front({1, 1, convert(a[1][1])});
  while (!dq.empty()) {
    auto [x, y, dir] = dq.front();
//    debug(x, y, dir);
    dq.pop_front();
    int r = x + movex[dir];
    int c = y + movey[dir];
    if (r > 0 and c > 0 and r <= n and c <= m and a[x][y] != 'X') {
      int nd = convert(a[r][c]);
      if (d[r][c][nd] > d[x][y][dir]) {
        d[r][c][nd] = d[x][y][dir];
        dq.push_front({r, c, nd});
      }
    }
    int nd = (dir + 1) % 4;
    if (d[x][y][nd] > d[x][y][dir] + 1) {
      d[x][y][nd] = d[x][y][dir] + 1;
      dq.emplace_back(x, y, nd);
    }
  }
  int res = 1e9;
  for (int i = 0; i < 4; ++i) {
    res = min(res, d[n][m][i]);
  }
  cout << (res == 1e9 ? -1 : res);;
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  solve();

  return 0;
}

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