Submission #577833

#	Time	Username	Problem	Language	Result	Execution time	Memory
577833		berr	Awesome Arrowland Adventure (eJOI19_adventure)	C++17	34 / 100	5 ms	4356 KiB

adventure

#include <bits/stdc++.h>
using namespace std;
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 1e9;

    if(grid[x][y]==-1) return 1e9;

    if(dp[x][y][z]!=-1) return dp[x][y][z];


    dp[x][y][z]=1e9;


    int diff=((((z-grid[x][y]+4)%4)));

    for(int i=0; i<4; i++)
    {

        
        if(z-i!=2&&z-i!=-2)
        {
        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=1e9;

     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<1e9) cout<<h;
    else cout<<-1;








}

Compilation message (stderr)

adventure.cpp: In function 'int32_t main()':
adventure.cpp:71:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   71 |     for(int i=0; i<505; i++)
      |     ^~~
adventure.cpp:77:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   77 |         int h=1e9;
      |         ^~~

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