Submission #631916

#	Time	Username	Problem	Language	Result	Execution time	Memory
631916		KALARRY	Awesome Arrowland Adventure (eJOI19_adventure)	C++14	100 / 100	107 ms	32176 KiB

adventure

#include<bits/stdc++.h>

using namespace std;

const long long INF = 1e14;

long long N,M,dist[250005];
vector<pair<long long,long long>> adj[250005];
bool visited[250005];

long long id(long long y,long long x)
{
    return (y-1)*N+x;
}
bool in_bounds(long long y,long long x)
{
    return 1<=x&&x<=N&&1<=y&&y<=M;
}

void dijkstra(long long start)
{
    priority_queue<pair<long long,long long>> q;
    for(long long i =1 ; i <= N*M ; i++)
        dist[i]=INF;
    dist[start]=0;
    q.push({0,start});
    while(!q.empty())
    {
        long long v= q.top().second;
        q.pop();
        if(visited[v])
            continue;
        visited[v]=true;
        for(auto e : adj[v])
        {
            long long w = e.first;
            long long u = e.second;
            if(dist[v]+w<dist[u])
            {
                dist[u]=dist[v]+w;
                q.push({-dist[u],u});        
            }
        }
    }
}
int main()
{
    scanf("%lld%lld",&M,&N);    
    for(long long i =1 ; i <= M ; i++)
    {
        for(long long j = 1 ; j <= N ; j++)
        {
            char arrow;
            scanf(" %c",&arrow);
            if(arrow=='E')
            {
                if(in_bounds(i,j+1))
                    adj[id(i,j)].push_back({0,id(i,j+1)});
                if(in_bounds(i+1,j))
                    adj[id(i,j)].push_back({1,id(i+1,j)});
                if(in_bounds(i,j-1))
                    adj[id(i,j)].push_back({2,id(i,j-1)});
                if(in_bounds(i-1,j))
                    adj[id(i,j)].push_back({3,id(i-1,j)});
            }
            if(arrow=='S')
            {
                if(in_bounds(i+1,j))
                    adj[id(i,j)].push_back({0,id(i+1,j)});
                if(in_bounds(i,j-1))
                    adj[id(i,j)].push_back({1,id(i,j-1)});
                if(in_bounds(i-1,j))
                    adj[id(i,j)].push_back({2,id(i-1,j)});
                if(in_bounds(i,j+1))
                    adj[id(i,j)].push_back({3,id(i,j+1)});
            }
            if(arrow=='W')
            {
                if(in_bounds(i,j-1))
                    adj[id(i,j)].push_back({0,id(i,j-1)});
                if(in_bounds(i-1,j))
                    adj[id(i,j)].push_back({1,id(i-1,j)});
                if(in_bounds(i,j+1))
                    adj[id(i,j)].push_back({2,id(i,j+1)});
                if(in_bounds(i+1,j))
                    adj[id(i,j)].push_back({3,id(i+1,j)});
            }
            if(arrow=='N')
            {
                if(in_bounds(i-1,j))
                    adj[id(i,j)].push_back({0,id(i-1,j)});
                if(in_bounds(i,j+1))
                    adj[id(i,j)].push_back({1,id(i,j+1)});
                if(in_bounds(i+1,j))
                    adj[id(i,j)].push_back({2,id(i+1,j)});
                if(in_bounds(i,j-1))
                    adj[id(i,j)].push_back({3,id(i,j-1)});
            }
            if(arrow=='X')
                visited[id(i,j)]=true;
        }
    }
    dijkstra(1);
    if(dist[id(M,N)]==INF)
        printf("-1\n");
    else
        printf("%lld\n",dist[id(M,N)]);
    return 0;
}

Compilation message (stderr)

adventure.cpp: In function 'int main()':
adventure.cpp:48:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |     scanf("%lld%lld",&M,&N);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
adventure.cpp:54:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |             scanf(" %c",&arrow);
      |             ~~~~~^~~~~~~~~~~~~~

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