Submission #1273431

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273431		matthew	Awesome Arrowland Adventure (eJOI19_adventure)	C++20	100 / 100	43 ms	4704 KiB

adventure

#include <stdio.h>
#include <ctype.h>
#include <queue>

const int MAX_N = 500;
const int MAX_M = 500;
const int INF = 1e9;

int n, m;
char mat[MAX_N][MAX_M];
int ans[MAX_N][MAX_M];

const int NDIR = 4;
int dlin[NDIR] = {-1, 0, 1, 0};
int dcol[NDIR] = {0, 1, 0, -1};

struct State {
  int l, c;
  int ans;

  bool operator <(const State& other) const {
    return ans > other.ans;
  }
};

bool inside(int l, int c) {
  return l >= 0 && l < n && c >= 0 && c < m;
}

char next_char() {
  char ch;
  while(isspace(ch = fgetc(stdin)));
  return ch;
}

void relax(int l, int c, int dir, int delta, std::priority_queue<State>& pq) {
  int nl = l + dlin[dir];
  int nc = c + dcol[dir];
  int new_ans = ans[l][c] + delta;
  if(inside(nl, nc) && new_ans < ans[nl][nc]) {
    ans[nl][nc] = new_ans;
    pq.push({nl, nc, new_ans});
  }
}

void bfs(int lin, int col) {
  for(int l = 0; l < n; l++) {
    for(int c = 0; c < m; c++) {
      ans[l][c] = INF;
    }
  }
  std::priority_queue<State> pq;
  pq.push({lin, col, 0});
  ans[lin][col] = 0;
  while(!pq.empty()) {
    State p = pq.top();
    int l = p.l;
    int c = p.c;
    int anss = p.ans;
    pq.pop();
    if(anss == ans[l][c]) {
      if(mat[l][c] == 4) continue;
      for(int d = 0; d < NDIR; d++) {
        int dir = (mat[l][c] + d) % 4;
        relax(l, c, dir, d, pq);
      }
    }
  }
}

int main() {
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
#endif

  scanf("%d%d", &n, &m);

  for(int l = 0; l < n; l++) {
    for(int c = 0; c < m; c++) {
      mat[l][c] = next_char();

      if(mat[l][c] == 'N') {
        mat[l][c] = 0;
      } else if(mat[l][c] == 'E') {
        mat[l][c] = 1;
      } else if(mat[l][c] == 'S') {
        mat[l][c] = 2;
      } else if(mat[l][c] == 'W') {
        mat[l][c] = 3;
      } else {
        mat[l][c] = 4;
      }
    }
  }

  bfs(0, 0);

  int res = ans[n - 1][m - 1];
  printf("%d\n", (res == INF) ? -1 : res);

  return 0;
}

Compilation message (stderr)

adventure.cpp: In function 'int main()':
adventure.cpp:76:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |   scanf("%d%d", &n, &m);
      |   ~~~~~^~~~~~~~~~~~~~~~

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