oj.uz

Submission #1055097

# Submission time Handle Problem Language Result Execution time Memory
1055097 2024-08-12T14:36:43 Z ThommyDB Awesome Arrowland Adventure (eJOI19_adventure) C++17
22 / 100
 0 ms 348 KB 
#include<bits/stdc++.h>

using namespace std;

int m, n;
vector<vector<int>> grid;
vector<vector<int>> test;
int lowest_ans = 1e9;

int dfs(int x, int y, int turns){
    if(turns > lowest_ans) return -1;
    test[x][y]=min(test[x][y], turns);
    if(x==n-1 && y==m-1){
        lowest_ans=min(lowest_ans, turns);
        return turns;
    } 
    if(grid[x][y]==-1)return 1e9;
    int dir = grid[x][y];
    int ans = 1e9;
    if(x!=0)if(turns < test[x-1][y]) ans = min(ans, dfs(x-1, y, turns + (4>=dir?4-dir:4+4-dir))); // west
    if(x!=n-1)if(turns < test[x+1][y]) ans = min(ans, dfs(x+1, y, turns + (2>=dir?2-dir:2+4-dir))); // east
    if(y!=0)if(turns < test[x][y-1]) ans = min(ans, dfs(x, y-1, turns + (1>=dir?1-dir:1+4-dir))); // north
    if(y!=m-1)if(turns < test[x][y+1]) ans = min(ans, dfs(x, y+1, turns + (3>=dir?3-dir:3+4-dir))); // south
    return ans;
}

signed main(){
    cin >> m >> n;
    grid.resize(n, vector<int>(m));
    test.resize(n, vector<int>(m, 1e9));
    for(int i = 0; i < m; i++){
        for(int j = 0; j < n; j++){
            char dir;
            cin >> dir;
            if(dir=='N') grid[j][i] = 1;
            else if(dir=='E') grid[j][i] = 2;
            else if(dir=='S') grid[j][i] = 3;
            else if(dir=='W') grid[j][i] = 4;
            else grid[j][i]=-1;
        }
    }
    int ans = dfs(0, 0, 0);
    if(ans==1e9){
        cout << "-1\n";
    }
    else{
        cout << ans << "\n";
    }
    /*for(int i = 0; i < m; i++){
        for(int j =0; j < n; j++){
            if(test[j][i]==1e9)test[j][i]=-1;
            cout << test[j][i] << " ";
        }
        cout << "\n";
    }*/
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 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 348 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 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 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 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 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 0 ms 348 KB Output is correct
16 Correct 0 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 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 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 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 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 0 ms 348 KB Output is correct
16 Correct 0 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 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Incorrect 0 ms 348 KB Output isn't correct
23 Halted 0 ms 0 KB -