Submission #1262634

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262634		iordache_	Awesome Arrowland Adventure (eJOI19_adventure)	C++20	16 / 100	1 ms	2376 KiB

adventure

#include <bits/stdc++.h>
#define pb push_back
#define int long long
using namespace std;
const int N=5e2+5;
char v[N][N];
int dir[N][N];
int dp[N][3];
signed main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n,m;
    cin>>n>>m;
    char ch;
    for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) cin>>v[j][i];
    for(int i=1;i<=m;++i) for(int j=1;j<=n;++j)
    {
        if(v[i][j]=='X') continue;
        if(v[i][j]=='N') dir[i][j]=0;
        if(v[i][j]=='E') dir[i][j]=1;
        if(v[i][j]=='S') dir[i][j]=2;
        if(v[i][j]=='W') dir[i][j]=3;
    }
    //atentie la m=1!!!
    for(int i=1;i<=m;++i) dp[i][1]=dp[i][2]=1e18;
    dp[1][1]=0;
    if(v[1][1]!='X') dp[1][2]=(2-dir[1][1]+4)%4;
    for(int i=2;i<=m;++i)
    {
        if(v[i-1][1]!='X') dp[i][1]=min(dp[i][1],dp[i-1][1]+(1-dir[i-1][1]+4)%4);
        if(v[i-1][2]!='X') dp[i][2]=min(dp[i][2],dp[i-1][2]+(1-dir[i-1][2]+4)%4);
        int a=dp[i][1],b=dp[i][2];
        if(v[i][2]!='X') dp[i][1]=min(dp[i][1],b+(0-dir[i][2]+4)%4);
        if(v[i][1]!='X') dp[i][2]=min(dp[i][2],a+(2-dir[i][1]+4)%4);
    }
    cout<<(dp[m][2]==1e18 ? -1:dp[m][2]);
}

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