제출 #1284021

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

adventure

#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<string> g(n);
    for (string &s : g) cin >> s;
    if (n == 1 && m == 1) {
        cout << 0;
        return 0;
    }   
    if (g[0][0] == 'X') {
        cout << -1;
        return 0;
    }
    string dir = "NESW";
    int dx[4] = {-1, 0, 1, 0};
    int dy[4] = {0, 1, 0, -1};
    const int inf = 1e9;
    vector<vector<int>> d(n, vector<int>(m, inf));
    d[0][0] = 0;
    priority_queue<tuple<int, int, int>> q;
    q.emplace(0, 0, 0);
    while (!q.empty()) {
        auto [dis, x, y] = q.top();
        dis = -dis;
        q.pop();
        int p = dir.find(g[x][y]);
        for (int k = 0; k < 4; k++) {
            int r = x + dx[(p + k) % 4], c = y + dy[(p + k) % 4];
            if (min({r, c, n - r - 1, m - c - 1}) >= 0) {
                int nd = d[x][y] + k;
                if (nd < d[r][c]) {
                    d[r][c] = nd;
                    if (g[r][c] == 'X') continue;
                    q.emplace(-nd, r, c);
                }
            }
        }
    }
    cout << (d[n - 1][m - 1] == inf ? -1 : d[n - 1][m - 1]);
    return 0;
}

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