제출 #972850

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
972850		vjudge1	Awesome Arrowland Adventure (eJOI19_adventure)	C++17	50 / 100	2058 ms	1628 KiB

adventure

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int INF = 1e8;
const int N = 505;
vector<vector<int>>dist(N, vector<int>(N, INF));
char grid[N][N];
map<char, int>mp;

int dx(int c){
    if(c%4 == 0) return -1;
    if(c%4 == 2) return 1;
    return 0;
    return 0;
}

int dy(int c){
    if(c%4 == 1) return 1;
    if(c%4 == 3) return -1;
    return 0;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    mp['N'] = 0; mp['E'] = 1; mp['S'] = 2; mp['W'] = 3;
    int R, C; cin >> R >> C;

    for(int i = 1; i <= R; i++){
        for(int j = 1; j <= C; j++)
            cin >> grid[i][j];
    }  

    dist[1][1] = 0;
    priority_queue<tuple<int, int, int>>q; q.emplace(0, 1, 1);

    const auto ok = [&](int x, int y) -> bool {
        return (1 <= x && x <= R && 1 <= y && y <= C);
    };

    while(!q.empty()){
        auto [d, x, y] = q.top(); q.pop();
        if(grid[x][y] == 'X') continue;
        if(d > dist[x][y]) continue;

        for(int i = 0; i <= 3; i++){
            int nx = x + dx(mp[grid[x][y]] + i);
            int ny = y + dy(mp[grid[x][y]] + i);

            if(ok(nx, ny) && dist[nx][ny] > dist[x][y] + i){
                dist[nx][ny] = dist[x][y] + i;
                q.emplace(dist[nx][ny], nx, ny);
            }
        }
    }

    if(dist[R][C] == INF) dist[R][C] = -1;
    cout << dist[R][C] << '\n';

    return 0;
}

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