Submission #759709

#	Time	Username	Problem	Language	Result	Execution time	Memory
759709		ivaziva	Awesome Arrowland Adventure (eJOI19_adventure)	C++14	12 / 100	1 ms	468 KiB

adventure

#include <bits/stdc++.h>

using namespace std;

#define MAXM 510
#define MAXN 1510

long long n;
long long m;
char matrica[MAXM][10];
vector<pair<long long,long long>> adj[MAXM];
long long dist[MAXN];

void dikstra(long long poc)
{
    for (long long i=0;i<MAXN;i++) dist[i]=LLONG_MAX;
    dist[poc]=0;
    priority_queue<pair<long long,long long>,vector<pair<long long,long long>>,greater<pair<long long,long long>>> pq;
    pq.push({0,poc});
    while (pq.empty()==false)
    {
        long long node0=pq.top().second;
        long long dist0=pq.top().first;
        pq.pop();
        if (dist0!=dist[node0]) continue;
        long long s=adj[node0].size();
        for (long long i=0;i<s;i++)
        {
            long long node=adj[node0][i].first;
            long long distt=adj[node0][i].second;
            if (dist0+distt<dist[node])
            {
                dist[node]=distt+dist0;
                pq.push({dist[node],node});
            }
        }
    }
}

int main()
{
    cin>>n>>m;
    for (long long i=1;i<=n;i++)
    {
        for (long long j=1;j<=m;j++) cin>>matrica[i][j];
    }
    for (long long i=1;i<=n;i++)
    {
        for (long long j=1;j<=m;j++)
        {
            if (i==1)
            {
                if (j==1)
                {
                    if (matrica[i][j]=='E')
                    {
                        adj[(i-1)*m+j].push_back({(i-1)*m+j+1,0});
                        adj[(i-1)*m+j].push_back({(i-1+1)*m+j,1});
                    }
                    if (matrica[i][j]=='S')
                    {
                        adj[(i-1)*m+j].push_back({(i-1)*m+j+1,3});
                        adj[(i-1)*m+j].push_back({(i-1+1)*m+j,0});
                    }
                    if (matrica[i][j]=='W')
                    {
                        adj[(i-1)*m+j].push_back({(i-1)*m+j+1,2});
                        adj[(i-1)*m+j].push_back({(i-1+1)*m+j,3});
                    }
                    if (matrica[i][j]=='N')
                    {
                        adj[(i-1)*m+j].push_back({(i-1)*m+j+1,1});
                        adj[(i-1)*m+j].push_back({(i-1+1)*m+j,2});
                    }
                }
                else if (j==m)
                {
                    if (matrica[i][j]=='E')
                    {
                        adj[(i-1)*m+j].push_back({(i-1)*m+j-1,2});
                        adj[(i-1)*m+j].push_back({(i-1+1)*m+j,1});
                    }
                    if (matrica[i][j]=='S')
                    {
                        adj[(i-1)*m+j].push_back({(i-1)*m+j-1,1});
                        adj[(i-1)*m+j].push_back({(i-1+1)*m+j,0});
                    }
                    if (matrica[i][j]=='W')
                    {
                        adj[(i-1)*m+j].push_back({(i-1)*m+j-1,0});
                        adj[(i-1)*m+j].push_back({(i-1+1)*m+j,3});
                    }
                    if (matrica[i][j]=='N')
                    {
                        adj[(i-1)*m+j].push_back({(i-1)*m+j-1,3});
                        adj[(i-1)*m+j].push_back({(i-1+1)*m+j,2});
                    }
                }
                else
                {
                    if (matrica[i][j]=='E')
                    {
                        adj[(i-1)*m+j].push_back({(i-1)*m+j+1,0});
                        adj[(i-1)*m+j].push_back({(i-1)*m+j-1,2});
                        adj[(i-1)*m+j].push_back({(i-1+1)*m+j,1});
                    }
                    if (matrica[i][j]=='S')
                    {
                        adj[(i-1)*m+j].push_back({(i-1)*m+j+1,3});
                        adj[(i-1)*m+j].push_back({(i-1)*m+j-1,1});
                        adj[(i-1)*m+j].push_back({(i-1+1)*m+j,0});
                    }
                    if (matrica[i][j]=='W')
                    {
                        adj[(i-1)*m+j].push_back({(i-1)*m+j+1,2});
                        adj[(i-1)*m+j].push_back({(i-1)*m+j-1,0});
                        adj[(i-1)*m+j].push_back({(i-1+1)*m+j,3});
                    }
                    if (matrica[i][j]=='N')
                    {
                        adj[(i-1)*m+j].push_back({(i-1)*m+j+1,1});
                        adj[(i-1)*m+j].push_back({(i-1)*m+j-1,3});
                        adj[(i-1)*m+j].push_back({(i-1+1)*m+j,2});
                    }
                }
            }
            else if (i==n)
            {
                if (j==1)
                {
                    if (matrica[i][j]=='E')
                    {
                        adj[(i-1)*m+j].push_back({(i-1)*m+j+1,0});
                        adj[(i-1)*m+j].push_back({(i-1-1)*m+j,3});
                    }
                    if (matrica[i][j]=='S')
                    {
                        adj[(i-1)*m+j].push_back({(i-1)*m+j+1,3});
                        adj[(i-1)*m+j].push_back({(i-1-1)*m+j,2});
                    }
                    if (matrica[i][j]=='W')
                    {
                        adj[(i-1)*m+j].push_back({(i-1)*m+j+1,2});
                        adj[(i-1)*m+j].push_back({(i-1-1)*m+j,1});
                    }
                    if (matrica[i][j]=='N')
                    {
                        adj[(i-1)*m+j].push_back({(i-1)*m+j+1,1});
                        adj[(i-1)*m+j].push_back({(i-1-1)*m+j,0});
                    }
                }
                else if (j==m)
                {
                    if (matrica[i][j]=='E')
                    {
                        adj[(i-1)*m+j].push_back({(i-1)*m+j-1,2});
                        adj[(i-1)*m+j].push_back({(i-1-1)*m+j,3});
                    }
                    if (matrica[i][j]=='S')
                    {
                        adj[(i-1)*m+j].push_back({(i-1)*m+j-1,1});
                        adj[(i-1)*m+j].push_back({(i-1-1)*m+j,2});
                    }
                    if (matrica[i][j]=='W')
                    {
                        adj[(i-1)*m+j].push_back({(i-1)*m+j-1,0});
                        adj[(i-1)*m+j].push_back({(i-1-1)*m+j,1});
                    }
                    if (matrica[i][j]=='N')
                    {
                        adj[(i-1)*m+j].push_back({(i-1)*m+j-1,3});
                        adj[(i-1)*m+j].push_back({(i-1-1)*m+j,0});
                    }
                }
                else
                {
                    if (matrica[i][j]=='E')
                    {
                        adj[(i-1)*m+j].push_back({(i-1)*m+j+1,0});
                        adj[(i-1)*m+j].push_back({(i-1)*m+j-1,2});
                        adj[(i-1)*m+j].push_back({(i-1-1)*m+j,3});
                    }
                    if (matrica[i][j]=='S')
                    {
                        adj[(i-1)*m+j].push_back({(i-1)*m+j+1,3});
                        adj[(i-1)*m+j].push_back({(i-1)*m+j-1,1});
                        adj[(i-1)*m+j].push_back({(i-1-1)*m+j,2});
                    }
                    if (matrica[i][j]=='W')
                    {
                        adj[(i-1)*m+j].push_back({(i-1)*m+j+1,2});
                        adj[(i-1)*m+j].push_back({(i-1)*m+j-1,0});
                        adj[(i-1)*m+j].push_back({(i-1-1)*m+j,1});
                    }
                    if (matrica[i][j]=='N')
                    {
                        adj[(i-1)*m+j].push_back({(i-1)*m+j+1,1});
                        adj[(i-1)*m+j].push_back({(i-1)*m+j-1,3});
                        adj[(i-1)*m+j].push_back({(i-1-1)*m+j,0});
                    }
                }
            }
            else
            {
                if (j==1)
                {
                    if (matrica[i][j]=='E')
                    {
                        adj[(i-1)*m+j].push_back({(i-1)*m+j+1,0});
                        adj[(i-1)*m+j].push_back({(i-1-1)*m+j,3});
                        adj[(i-1)*m+j].push_back({(i-1+1)*m+j,1});
                    }
                    if (matrica[i][j]=='S')
                    {
                        adj[(i-1)*m+j].push_back({(i-1)*m+j+1,3});
                        adj[(i-1)*m+j].push_back({(i-1-1)*m+j,2});
                        adj[(i-1)*m+j].push_back({(i-1+1)*m+j,0});
                    }
                    if (matrica[i][j]=='W')
                    {
                        adj[(i-1)*m+j].push_back({(i-1)*m+j+1,2});
                        adj[(i-1)*m+j].push_back({(i-1-1)*m+j,1});
                        adj[(i-1)*m+j].push_back({(i-1+1)*m+j,3});
                    }
                    if (matrica[i][j]=='N')
                    {
                        adj[(i-1)*m+j].push_back({(i-1)*m+j+1,1});
                        adj[(i-1)*m+j].push_back({(i-1-1)*m+j,0});
                        adj[(i-1)*m+j].push_back({(i-1+1)*m+j,2});
                    }
                }
                else if (j==m)
                {
                    if (matrica[i][j]=='E')
                    {
                        adj[(i-1)*m+j].push_back({(i-1)*m+j-1,2});
                        adj[(i-1)*m+j].push_back({(i-1-1)*m+j,3});
                        adj[(i-1)*m+j].push_back({(i-1+1)*m+j,1});
                    }
                    if (matrica[i][j]=='S')
                    {
                        adj[(i-1)*m+j].push_back({(i-1)*m+j-1,1});
                        adj[(i-1)*m+j].push_back({(i-1-1)*m+j,2});
                        adj[(i-1)*m+j].push_back({(i-1+1)*m+j,0});
                    }
                    if (matrica[i][j]=='W')
                    {
                        adj[(i-1)*m+j].push_back({(i-1)*m+j-1,0});
                        adj[(i-1)*m+j].push_back({(i-1-1)*m+j,1});
                        adj[(i-1)*m+j].push_back({(i-1+1)*m+j,3});
                    }
                    if (matrica[i][j]=='N')
                    {
                        adj[(i-1)*m+j].push_back({(i-1)*m+j-1,3});
                        adj[(i-1)*m+j].push_back({(i-1-1)*m+j,0});
                        adj[(i-1)*m+j].push_back({(i-1+1)*m+j,2});
                    }
                }
                else
                {
                    if (matrica[i][j]=='E')
                    {
                        adj[(i-1)*m+j].push_back({(i-1)*m+j+1,0});
                        adj[(i-1)*m+j].push_back({(i-1)*m+j-1,2});
                        adj[(i-1)*m+j].push_back({(i-1-1)*m+j,3});
                        adj[(i-1)*m+j].push_back({(i-1+1)*m+j,1});
                    }
                    if (matrica[i][j]=='S')
                    {
                        adj[(i-1)*m+j].push_back({(i-1)*m+j+1,3});
                        adj[(i-1)*m+j].push_back({(i-1)*m+j-1,1});
                        adj[(i-1)*m+j].push_back({(i-1-1)*m+j,2});
                        adj[(i-1)*m+j].push_back({(i-1+1)*m+j,0});
                    }
                    if (matrica[i][j]=='W')
                    {
                        adj[(i-1)*m+j].push_back({(i-1)*m+j+1,2});
                        adj[(i-1)*m+j].push_back({(i-1)*m+j-1,0});
                        adj[(i-1)*m+j].push_back({(i-1-1)*m+j,1});
                        adj[(i-1)*m+j].push_back({(i-1+1)*m+j,3});
                    }
                    if (matrica[i][j]=='N')
                    {
                        adj[(i-1)*m+j].push_back({(i-1)*m+j+1,1});
                        adj[(i-1)*m+j].push_back({(i-1)*m+j-1,3});
                        adj[(i-1)*m+j].push_back({(i-1-1)*m+j,0});
                        adj[(i-1)*m+j].push_back({(i-1+1)*m+j,2});
                    }
                }
            }
        }
    }
    dikstra(1);
    if (dist[n*m]==LLONG_MAX) cout<<-1<<endl;
    else cout<<dist[n*m]<<endl;
}

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