제출 #976698

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

adventure

#include "bits/stdc++.h"
using namespace std;
#define int long long
#define ll long long
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define sz size
#define fr front 
#define bc backn
#define pii pair<int,int>
#define all(x) x.begin() , x.end()
#define cmin(a, b) a = min(a , b)
#define cmax(a, b) a = max(a, b)
#define mems(arr , a) memset(arr , a , sizeof arr)
#define each(i , arr) for(auto &i : arr)
const int MOD = 1e9 + 7;
const int INF = 1e18;
#define state tuple<int,int,int,int>

int n , m;
int dx[4] = {-1 , 0 , 1 , 0};
int dy[4] = {0 , 1 , 0 , -1};

int getdir(char c){
    if(c == 'N') return 0;
    if(c == 'E') return 1;
    if(c == 'S') return 2;
    if(c == 'W') return 3;
    return 4;
}

bool valid(int x , int y){
    if(x >= 1 && x <= n && y >= 1 && y <= m) return 1;
    return 0;
}

signed main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t;  
    t = 1;
    // cin >> t;
    while(t--){
       
       cin >> n >> m;
       int dist[n+1][m+1][5];
       char grid[n+1][m+1];
       for(int i = 1; i <= n; i++){
           for(int j = 1; j <= m; j++){
               cin >> grid[i][j];
               for(int k = 0; k < 5; k++){
                   dist[i][j][k] = INF;
               }
           }
       }
        priority_queue<state , vector<state> , greater<state>> pq;
        dist[1][1][getdir(grid[1][1])] = 0;
        pq.push({0 , 1 , 1 , getdir(grid[1][1])});
        while(!pq.empty()){
            auto [cost , r , c , dir] = pq.top();
            pq.pop();
            if(dir == 4) continue;
            int nR = r + dx[dir] , nC = c + dy[dir];
            if(valid(nR , nC)){
                int nD = getdir(grid[nR][nC]);
                if(cost < dist[nR][nC][nD]){
                    dist[nR][nC][nD] = cost;
                    pq.push({cost , nR , nC , nD});
                }
            }

            dir = (dir+1) % 4;
            if(cost+1 < dist[r][c][dir]){
                dist[r][c][dir] = cost+1;
                pq.push({cost+1 , r , c , dir});
            }
            
        }
        // cout << dist[n][m] << ' ';
        if(dist[n][m][4] == INF) dist[n][m][4] = -1;
        cout << dist[n][m][4];
    }

}

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