Submission #1161349

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161349		pridelique	Awesome Arrowland Adventure (eJOI19_adventure)	C++20	0 / 100	0 ms	328 KiB

adventure

#include<bits/stdc++.h>
using namespace std;
#define int long long
struct st
{
    int i,j,d;
};
signed main()
{
    int n,m;
    cin>>n>>m;
    int dist[n][m];
    string s[n];
    for(int i=0;i<n;i++)
    cin>>s[i];
    queue<st> q;
    q.push({0,0,0});
    memset(dist,127,sizeof dist);
    dist[0][0]=0;
    while(!q.empty())
    {
        auto p=q.front();
        q.pop();
        int i=p.i,j=p.j,d=p.d;
        if(d>dist[i][j])
        continue;
        if(i+1>=0&&i+1<n&&j>=0&&j<m&&(s[i+1][j]!='X'||(i+1==n-1&&j==m-1)))
        {
            if(s[i][j]=='S'&&dist[i+1][j]>d)
            {
                dist[i+1][j]=d;
                q.push({i+1,j,d});
            }
            else if(s[i][j]=='E'&&dist[i+1][j]>d+1)
            {
                dist[i+1][j]=d+1;
                q.push({i+1,j,d+1});
            }
            else if(s[i][j]=='N'&&dist[i+1][j]>d+2)
            {
                dist[i+1][j]=d+2;
                q.push({i+1,j,d+2});
            }
            else if(s[i][j]=='W'&&dist[i+1][j]>d+3)
            {
                dist[i+1][j]=d+3;
                q.push({i+1,j,d+3});
            }
        }
        if(i-1>=0&&i-1<n&&j>=0&&j<m&&(s[i-1][j]!='X'||(i-1==n-1&&j==m-1)))
        {
            if(s[i][j]=='N'&&dist[i-1][j]>d)
            {
                dist[i-1][j]=d;
                q.push({i-1,j,d});
            }
            else if(s[i][j]=='W'&&dist[i-1][j]>d+1)
            {
                dist[i-1][j]=d+1;
                q.push({i-1,j,d+1});
            }
            else if(s[i][j]=='S'&&dist[i-1][j]>d+2)
            {
                dist[i-1][j]=d+2;
                q.push({i-1,j,d+2});
            }
            else if(s[i][j]=='E'&&dist[i-1][j]>d+3)
            {
                dist[i-1][j]=d+3;
                q.push({i-1,j,d+3});
            }
        }
        if(i>=0&&i<n&&j+1>=0&&j+1<m&&(s[i][j+1]!='X'||(i==n-1&&j+1==m-1)))
        {
            if(s[i][j]=='E'&&dist[i][j+1]>d)
            {
                dist[i][j+1]=d;
                q.push({i,j+1,d});
            }
            else if(s[i][j]=='N'&&dist[i][j+1]>d+1)
            {
                dist[i][j+1]=d+1;
                q.push({i,j+1,d+1});
            }
            else if(s[i][j]=='W'&&dist[i][j+1]>d+2)
            {
                dist[i][j+1]=d+2;
                q.push({i,j+1,d+2});
            }
            else if(s[i][j]=='S'&&dist[i][j+1]>d+3)
            {
                dist[i][j+1]=d+3;
                q.push({i,j+1,d+3});
            }
        }
        if(i>=0&&i<n&&j-1>=0&&j-1<m&&(s[i][j-1]!='X'||(i==n-1&&j-1==m-1)))
        {
            if(s[i][j]=='W'&&dist[i][j-1]>d)
            {
                dist[i][j-1]=d;
                q.push({i,j-1,d});
            }
            else if(s[i][j]=='S'&&dist[i][j-1]>d+1)
            {
                dist[i][j-1]=d+1;
                q.push({i,j-1,d+1});
            }
            else if(s[i][j]=='E'&&dist[i][j-1]>d+2)
            {
                dist[i][j-1]=d+2;
                q.push({i,j-1,d+2});
            }
            else if(s[i][j]=='N'&&dist[i][j-1]>d+3)
            {
                dist[i][j-1]=d+3;
                q.push({i,j-1,d+3});
            }
        }
    }
    if(dist[n-1][m-1]==LLONG_MAX)
    cout<<-1;
    else
    cout<<dist[n-1][m-1];
    /*for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        cout<<dist[i][j]<<" ";
        cout<<endl;
    }*/
}

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