oj.uz

답안 #577834

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
577834 2022-06-15T09:55:21 Z berr Awesome Arrowland Adventure (eJOI19_adventure) C++17
34 / 100
 8 ms 8368 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long

int dp[505][505][4], grid[504][504];
int n, m;
 
array<int, 4> c{0, 1, 0, -1};
array<int, 4> b{-1, 0, 1, 0};
 
 
 
int f(int x, int y, int z)
{   
 
 
    if(x==n-1&&y==m-1) return 0;
 
    if(x<0||x>=n||y>=m||y<0) return 1e16;
 
    if(grid[x][y]==-1) return 1e16;
 
    if(dp[x][y][z]!=-1) return dp[x][y][z];
 
 
    dp[x][y][z]=1e16;
 
 
    int diff=((((z-grid[x][y]+4)%4)));
 
    for(int i=0; i<4; i++)
    {
 
        
     
        int xe=x+b[z], ye=y+c[z];
        
        int p=f(xe, ye, i);
 
        if(dp[x][y][z]>p+diff)
        dp[x][y][z]=p+diff;
        
 
    }
    return dp[x][y][z];
}
int32_t main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
 
    cin>>n>>m;
 
 
    f(1, 2, 0);
    for(int i=0; i<n; i++)
    {
        for(int l=0; l<m; l++)
        {
            char x; cin>>x;
            if(x=='N') grid[i][l]=0;
            if(x=='E') grid[i][l]=1;
            if(x=='S') grid[i][l]=2;
            if(x=='W') grid[i][l]=3;
            if(x=='X') grid[i][l]=-1; 
 
            dp[i][l][0]=dp[i][l][1]=dp[i][l][2]=dp[i][l][3]=-1;
        }
    }
 
 
    for(int i=0; i<505; i++)
        for(int l=0; l<505; l++)
            dp[i][l][0]=dp[i][l][1]=dp[i][l][2]=dp[i][l][3]=-1;
 
 
 
        int h=1e16;
 
     h=min({h, f(0, 0,0)});
        for(int i=0; i<505; i++)
        for(int l=0; l<505; l++)
            dp[i][l][0]=dp[i][l][1]=dp[i][l][2]=dp[i][l][3]=-1;
 
 
    h=min(h, f(0, 0, 1));
        for(int i=0; i<505; i++)
        for(int l=0; l<505; l++)
            dp[i][l][0]=dp[i][l][1]=dp[i][l][2]=dp[i][l][3]=-1;
 
    h=min(h, f(0, 0, 3));
        for(int i=0; i<505; i++)
        for(int l=0; l<505; l++)
            dp[i][l][0]=dp[i][l][1]=dp[i][l][2]=dp[i][l][3]=-1;
 
        h=min(h ,f(0, 0, 2));
 
 
 
    if(h<1e16) cout<<h;
    else cout<<-1;
 
 
 
 
 
 
 
 
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 8276 KB Output is correct
2 Correct 8 ms 8276 KB Output is correct
3 Correct 7 ms 8276 KB Output is correct
4 Correct 6 ms 8316 KB Output is correct
5 Correct 7 ms 8276 KB Output is correct
6 Correct 6 ms 8276 KB Output is correct
7 Correct 6 ms 8276 KB Output is correct
8 Correct 6 ms 8256 KB Output is correct
9 Correct 5 ms 8276 KB Output is correct
10 Correct 6 ms 8308 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 8276 KB Output is correct
2 Correct 8 ms 8276 KB Output is correct
3 Correct 7 ms 8276 KB Output is correct
4 Correct 6 ms 8316 KB Output is correct
5 Correct 7 ms 8276 KB Output is correct
6 Correct 6 ms 8276 KB Output is correct
7 Correct 6 ms 8276 KB Output is correct
8 Correct 6 ms 8256 KB Output is correct
9 Correct 5 ms 8276 KB Output is correct
10 Correct 6 ms 8308 KB Output is correct
11 Correct 6 ms 8228 KB Output is correct
12 Correct 6 ms 8276 KB Output is correct
13 Correct 7 ms 8276 KB Output is correct
14 Correct 5 ms 8276 KB Output is correct
15 Correct 6 ms 8276 KB Output is correct
16 Correct 7 ms 8368 KB Output is correct
17 Correct 7 ms 8276 KB Output is correct
18 Correct 7 ms 8276 KB Output is correct
19 Correct 5 ms 8276 KB Output is correct
20 Correct 5 ms 8276 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 8276 KB Output is correct
2 Correct 6 ms 8316 KB Output is correct
3 Correct 6 ms 8276 KB Output is correct
4 Correct 6 ms 8276 KB Output is correct

Subtask #4
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 8276 KB Output is correct
2 Incorrect 6 ms 8276 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 8276 KB Output is correct
2 Correct 8 ms 8276 KB Output is correct
3 Correct 7 ms 8276 KB Output is correct
4 Correct 6 ms 8316 KB Output is correct
5 Correct 7 ms 8276 KB Output is correct
6 Correct 6 ms 8276 KB Output is correct
7 Correct 6 ms 8276 KB Output is correct
8 Correct 6 ms 8256 KB Output is correct
9 Correct 5 ms 8276 KB Output is correct
10 Correct 6 ms 8308 KB Output is correct
11 Correct 6 ms 8228 KB Output is correct
12 Correct 6 ms 8276 KB Output is correct
13 Correct 7 ms 8276 KB Output is correct
14 Correct 5 ms 8276 KB Output is correct
15 Correct 6 ms 8276 KB Output is correct
16 Correct 7 ms 8368 KB Output is correct
17 Correct 7 ms 8276 KB Output is correct
18 Correct 7 ms 8276 KB Output is correct
19 Correct 5 ms 8276 KB Output is correct
20 Correct 5 ms 8276 KB Output is correct
21 Correct 6 ms 8276 KB Output is correct
22 Correct 6 ms 8316 KB Output is correct
23 Correct 6 ms 8276 KB Output is correct
24 Correct 6 ms 8276 KB Output is correct
25 Correct 8 ms 8276 KB Output is correct
26 Incorrect 6 ms 8276 KB Output isn't correct
27 Halted 0 ms 0 KB -