Submission #655766

#	Time	Username	Problem	Language	Result	Execution time	Memory
655766		borisAngelov	Awesome Arrowland Adventure (eJOI19_adventure)	C++17	100 / 100	29 ms	25444 KiB

adventure

#include <iostream>
#include <utility>
#include <vector>
#include <tuple>
#include <queue>

using namespace std;

const int maxn = 505;
const int inf = 1000000007;

int n, m;

int table[maxn][maxn];

pair<int, int> dirs[4] = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};
int timeForChange[4][4];

void MakeChangeTime() {
    //W -> 0, N - 1, E - 2, S - 3
    timeForChange[0][0] = 0;
    timeForChange[0][1] = 1;
    timeForChange[0][2] = 2;
    timeForChange[0][3] = 3;

    timeForChange[1][0] = 3;
    timeForChange[1][1] = 0;
    timeForChange[1][2] = 1;
    timeForChange[1][3] = 2;

    timeForChange[2][0] = 2;
    timeForChange[2][1] = 3;
    timeForChange[2][2] = 0;
    timeForChange[2][3] = 1;

    timeForChange[3][0] = 1;
    timeForChange[3][1] = 2;
    timeForChange[3][2] = 3;
    timeForChange[3][3] = 0;
}

vector<pair<int, int>> minCoordinates[3 * maxn * maxn];
int dist[maxn][maxn];

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

    cin >> n >> m;

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            char c; cin >> c;

            if (c == 'W') table[i][j] = 0;
            if (c == 'N') table[i][j] = 1;
            if (c == 'E') table[i][j] = 2;
            if (c == 'S') table[i][j] = 3;
            if (c == 'X') table[i][j] = -1;
        }
    }

    if (table[1][1] == 'X') {
        cout << -1 << endl;
        return 0;
    }

    MakeChangeTime();

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            dist[i][j] = inf;
        }
    }

    dist[1][1] = 0;
    minCoordinates[0].push_back({1, 1});

    for (int path = 0; path <= 3 * n * m; ++path) {
        for (int idx = 0; idx < minCoordinates[path].size(); idx++) {
            int currX, currY;
            tie(currX, currY) = minCoordinates[path][idx];

            if (currX == n && currY == m) {
                cout << path << endl;
                exit(0);
            }

            if (dist[currX][currY] < path) continue;

            if (table[currX][currY] == -1) continue;

            for (int change = 0; change <= 3; change++) {
                int newX = currX + dirs[change].first;
                int newY = currY + dirs[change].second;

                if (newX < 1 || newX > n || newY < 1 || newY > m) continue;

                int currPath = path + timeForChange[table[currX][currY]][change];

                if (currPath < dist[newX][newY]) {
                    dist[newX][newY] = currPath;
                    minCoordinates[currPath].push_back({newX, newY});
                }
            }
        }
    }

    cout << -1 << endl;

    return 0;
}

Compilation message (stderr)

adventure.cpp: In function 'int main()':
adventure.cpp:79:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |         for (int idx = 0; idx < minCoordinates[path].size(); idx++) {
      |                           ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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