oj.uz

Submission #976299

# Submission time Handle Problem Language Result Execution time Memory
976299 2024-05-06T12:00:16 Z vjudge1 Awesome Arrowland Adventure (eJOI19_adventure) C++17
50 / 100
 2000 ms 1372 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 600 KB Output is correct
10 Correct 0 ms 348 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 600 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 600 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 344 KB Output is correct
20 Correct 0 ms 348 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 504 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 3 ms 348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 452 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct

Subtask #5
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 600 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 600 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 344 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 0 ms 504 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 344 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 3 ms 348 KB Output is correct
30 Correct 2 ms 348 KB Output is correct
31 Correct 1 ms 348 KB Output is correct
32 Correct 0 ms 452 KB Output is correct
33 Correct 1 ms 348 KB Output is correct
34 Correct 1 ms 348 KB Output is correct
35 Execution timed out 2055 ms 1372 KB Time limit exceeded
36 Halted 0 ms 0 KB -