Submission #976299

#	Time	Username	Problem	Language	Result	Execution time	Memory
976299		vjudge1	Awesome Arrowland Adventure (eJOI19_adventure)	C++17	50 / 100	2055 ms	1372 KiB

adventure

#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second 
int n, m, dp[505][505] = {0};
char g[505][505];
//          N  E  S  W
int N[4] = {0, 1, 2, 3};
int E[4] = {3, 0, 1, 2};
int S[4] = {2, 3, 0, 1};
int W[4] = {1, 2, 3, 0};
pair<int, int>p[4] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

void bf(int x, int y){
    if(g[x][y] == 'N'){
        for(int i = 0; i < 4; i++){
            if(dp[x][y] + N[i] < dp[x + p[i].F][y + p[i].S]){
               // cout << x << ',' << y << ' ' << dp[x][y] << ' ' << N[i] << endl;
                dp[x + p[i].F][y + p[i].S] = dp[x][y] + N[i];
                if(g[x + p[i].F][y + p[i].S] != 'X') bf(x + p[i].F, y + p[i].S);
            }
        }
    }else if(g[x][y] == 'E'){
        for(int i = 0; i < 4; i++){
            if(dp[x][y] + E[i] < dp[x + p[i].F][y + p[i].S]){
               // cout << x << ',' << y << ' ' << dp[x][y] << ' ' << N[i] << endl;
                dp[x + p[i].F][y + p[i].S] = dp[x][y] + E[i];
                if(g[x + p[i].F][y + p[i].S] != 'X') bf(x + p[i].F, y + p[i].S);
            }
        }
    }else if(g[x][y] == 'S'){
        for(int i = 0; i < 4; i++){
            if(dp[x][y] + S[i] < dp[x + p[i].F][y + p[i].S]){
               // cout << x << ',' << y << ' ' << dp[x][y] << ' ' << N[i] << endl;
                dp[x + p[i].F][y + p[i].S] = dp[x][y] + S[i];
                if(g[x + p[i].F][y + p[i].S] != 'X') bf(x + p[i].F, y + p[i].S);
            }
        }
    }else if(g[x][y] == 'W'){
        for(int i = 0; i < 4; i++){
            if(dp[x][y] + W[i] < dp[x + p[i].F][y + p[i].S]){
                //cout << x << ',' << y << ' ' << dp[x][y] << ' ' << N[i] << endl;
                dp[x + p[i].F][y + p[i].S] = dp[x][y] + W[i];
                if(g[x + p[i].F][y + p[i].S] != 'X') bf(x + p[i].F, y + p[i].S);
            }
        }
    }
}

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        g[i][0] = 'X'; dp[i][0] = 1e9+7;
    }
    for(int i = 1; i <= m; i++){
        g[0][i] = 'X'; dp[0][i] = 1e9+7;
    }
    
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            dp[i][j] = 1e9+7;
            cin >> g[i][j];
        }
    } 
    dp[1][1] = 0;
    bf(1, 1);
   /* for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++) cout << dp[i][j] << ' ';
        cout << endl;
    }*/
    if(dp[n][m] == 1e9+7) cout << -1;
    else cout << dp[n][m];
}
/*
N atas
E kanan
S bawah
W kiri

3 3
ENS
SXN
WSX
4 3
EES 
SWW
SES
ENX

2 2 
NN 
NN
*/

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