Submission #448806

#	Time	Username	Problem	Language	Result	Execution time	Memory
448806		radaiosm7	Awesome Arrowland Adventure (eJOI19_adventure)	C++98	100 / 100	117 ms	23332 KiB

adventure

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int n, m, i, j;
char s[505][505];
vector<pair<pair<int, int>, int> > adj[505][505];
int d[505][505];
pair<int, int> curr;
set<pair<int, pair<int, int> > > S;
const int INF = INT_MAX/2;

bool isValid(int x, int y) {
  return (x == n-1 && y == m-1) || (x >= 0 && x < n && y >= 0 && y < m && s[x][y] != 'X');
}

int main() {
  scanf("%d%d", &n, &m);

  for (i=0; i < n; ++i) scanf("\n%s", s[i]);

  for (i=0; i < n; ++i) {
    for (j=0; j < m; ++j) {
      if (s[i][j] == 'X') continue;

      else if (s[i][j] == 'W') {
        if (isValid(i, j-1)) adj[i][j].push_back(make_pair(make_pair(i, j-1), 0));
        if (isValid(i-1, j)) adj[i][j].push_back(make_pair(make_pair(i-1, j), 1));
        if (isValid(i, j+1)) adj[i][j].push_back(make_pair(make_pair(i, j+1), 2));
        if (isValid(i+1, j)) adj[i][j].push_back(make_pair(make_pair(i+1, j), 3));
      }

      else if (s[i][j] == 'N') {
        if (isValid(i-1, j)) adj[i][j].push_back(make_pair(make_pair(i-1, j), 0));
        if (isValid(i, j+1)) adj[i][j].push_back(make_pair(make_pair(i, j+1), 1));
        if (isValid(i+1, j)) adj[i][j].push_back(make_pair(make_pair(i+1, j), 2));
        if (isValid(i, j-1)) adj[i][j].push_back(make_pair(make_pair(i, j-1), 3));
      }

      else if (s[i][j] == 'E') {
        if (isValid(i, j+1)) adj[i][j].push_back(make_pair(make_pair(i, j+1), 0));
        if (isValid(i+1, j)) adj[i][j].push_back(make_pair(make_pair(i+1, j), 1));
        if (isValid(i, j-1)) adj[i][j].push_back(make_pair(make_pair(i, j-1), 2));
        if (isValid(i-1, j)) adj[i][j].push_back(make_pair(make_pair(i-1, j), 3));
      }

      else if (s[i][j] == 'S') {
        if (isValid(i+1, j)) adj[i][j].push_back(make_pair(make_pair(i+1, j), 0));
        if (isValid(i, j-1)) adj[i][j].push_back(make_pair(make_pair(i, j-1), 1));
        if (isValid(i-1, j)) adj[i][j].push_back(make_pair(make_pair(i-1, j), 2));
        if (isValid(i, j+1)) adj[i][j].push_back(make_pair(make_pair(i, j+1), 3));
      }
    }
  }

  for (i=0; i < n; ++i) for (j=0; j < m; ++j) d[i][j] = INF;
  d[0][0] = 0;
  S.insert(make_pair(0, make_pair(0,0)));

  while (!S.empty()) {
    curr = S.begin()->second;
    S.erase(S.begin());

    for (auto y : adj[curr.X][curr.Y]) {
      if (d[y.X.X][y.X.Y] > d[curr.X][curr.Y]+y.Y) {
        S.erase(make_pair(d[y.X.X][y.X.Y], y.X));
        d[y.X.X][y.X.Y] = d[curr.X][curr.Y]+y.Y;
        S.insert(make_pair(d[y.X.X][y.X.Y], y.X));
      }
    }
  }

  if (d[n-1][m-1] == INF) printf("-1\n");
  else printf("%d\n", d[n-1][m-1]);
  return 0;
}

Compilation message (stderr)

adventure.cpp: In function 'int main()':
adventure.cpp:18:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |   scanf("%d%d", &n, &m);
      |   ~~~~~^~~~~~~~~~~~~~~~
adventure.cpp:20:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |   for (i=0; i < n; ++i) scanf("\n%s", s[i]);
      |                         ~~~~~^~~~~~~~~~~~~~

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