제출 #1201221

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1201221		kelenjo	Awesome Arrowland Adventure (eJOI19_adventure)	C++20	100 / 100	40 ms	4796 KiB

adventure

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

using namespace std;

const int INF = 1e9;
int dx[4] = {0, 1, 0, -1};  // E, S, W, N
int dy[4] = {1, 0, -1, 0};

int main() {
    int n, m;
    cin >> n >> m;

    vector<vector<char>> grid(n, vector<char>(m));
    map<char, int> dirMap = {{'E', 0}, {'S', 1}, {'W', 2}, {'N', 3}};

    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            cin >> grid[i][j];

    vector<vector<int>> dist(n, vector<int>(m, INF));
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> pq;

    dist[0][0] = 0;
    pq.emplace(0, 0, 0);  // (rotations, x, y)

    while (!pq.empty()) {
        auto [rot, x, y] = pq.top(); pq.pop();

        if (make_pair(x, y) == make_pair(n - 1, m - 1)) {
            cout << rot << endl;
            return 0;
        }

        if (grid[x][y] == 'X') continue; // dead cell

        int currentDir = dirMap[grid[x][y]];
        for (int newDir = 0; newDir < 4; ++newDir) {
            int nx = x + dx[newDir];
            int ny = y + dy[newDir];
            if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
            if (grid[nx][ny] == 'X' && !(nx == n - 1 && ny == m - 1)) continue;

            int rotCost = (newDir - currentDir + 4) % 4;
            if (dist[nx][ny] > dist[x][y] + rotCost) {
                dist[nx][ny] = dist[x][y] + rotCost;
                pq.emplace(dist[nx][ny], nx, ny);
            }
        }
    }

    cout << -1 << endl;
    return 0;
}

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