Submission #1159922

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159922		fork1024	Awesome Arrowland Adventure (eJOI19_adventure)	C++20	100 / 100	65 ms	4796 KiB

adventure

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define ff first
#define ss second
//#define int long long
#define piii pair<int, pair<int, int>>
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
const int INF = 1e9;
const int N = 503;
char grid[N+1][N+1];
int shortest[N+1][N+1];

int needed[4][4] = {{0, 1, 2, 3}, {3, 0, 1, 2}, {2, 3, 0, 1}, {1, 2, 3, 0}};
                //  E   S   W   N


map<char, int> mp;

void djikstra(){
    priority_queue<piii, vector<piii>, greater<piii>> pq;

    //{dist, {x, y}}
    pq.push({0, {1, 1}});

    while(!pq.empty()){
        piii p = pq.top(); pq.pop();


        for(int i=0; i<4; i++){
            //4 variants -- E, S, W, N
        int newx = p.ss.ff+dx[i], newy = p.ss.ss+dy[i];

        int x = p.ss.ff, y = p.ss.ss;
            if(grid[x][y]=='X') break;
            
        if(shortest[newx][newy] > shortest[x][y] + needed[ mp[grid[x][y]] ][ i ]){

            //cout << mp[grid[x][y]] << endl;
            shortest[newx][newy] = shortest[x][y] + needed[ mp[grid[x][y]] ][ i ];
            pq.push({shortest[newx][newy], {newx, newy}});
        }

    }

}


}
void test(){
 

    //ifstream cin("perimeter.in");
	//ofstream cout("perimeter.out");
    
    int n, m;

    cin >> n >> m;

    mp['E'] = 0, mp['S'] = 1, mp['W'] = 2, mp['N'] = 3;

    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            cin >> grid[i][j];
            shortest[i][j] = INF;
        }
    }

    shortest[1][1] = 0;

    djikstra();

    if(shortest[n][m]==1e9) cout << -1 << endl; else cout << shortest[n][m] << endl;


}
int32_t main(){
     std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr); std::cout.tie(nullptr);
   //int t;
   //cin >> t;
    //while(t--)
    test();
}

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