Submission #1165939

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165939		filipsumic	Awesome Arrowland Adventure (eJOI19_adventure)	C++20	100 / 100	63 ms	21948 KiB

adventure

#include <bits/stdc++.h>
#define pb push_back
#define ll long long int
#define pi pair<int, int>
#define all(x) x.begin(), x.end()
#define INF INT_MAX
using namespace std;

int Oduzmi(int a, int b)
{
    if(a>=b) return a-b;
    return 4-b+a;
}
void Dijkstra(vector<vector<pi>>& graf,  vector<int>& distance, vector<bool>& visited)
{
    priority_queue<pi, vector<pi>, greater<pi>> pq;
    pq.push({0, 0});
    while(!pq.empty())
    {
        pi sad=pq.top();
        int cvor=sad.second, dist=sad.first;
        pq.pop();
        if(visited[cvor]) continue;
        visited[cvor]=true;
        for(auto u:graf[cvor])
        {
            int sl=u.second, d=u.first;
            if(d+dist<distance[sl])
            {
                distance[sl]=d+dist;
                pq.push({distance[sl], sl});
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin>>n>>m;
    vector<vector<int>> mat(n);
    for(int i=0; i<n; i++)
    {
        mat[i].resize(m);
        for(int j=0; j<m; j++)
        {
            char un;
            cin>>un;
            if(un=='N') mat[i][j]=0;
            else if(un=='E') mat[i][j]=1;
            else if(un=='S') mat[i][j]=2;
            else if(un=='W') mat[i][j]=3;
            else mat[i][j]=-1;
        }
    }
    vector<vector<pi>> graf(n*m+5);
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
            if(mat[i][j]==-1) continue;
            int ind=i*m+j, gore=(i-1)*m+j, desno=i*m+j+1, dole=(i+1)*m+j, levo=i*m+j-1;
            if(i>0) graf[ind].pb({Oduzmi(0, mat[i][j]), gore});
            if(i<n-1) graf[ind].pb({Oduzmi(2, mat[i][j]), dole});
            if(j>0) graf[ind].pb({Oduzmi(3, mat[i][j]), levo});
            if(j<m-1) graf[ind].pb({Oduzmi(1, mat[i][j]), desno});
        }
    }
    vector<int> distance(n*m, INF);
    vector<bool> visited(n*m, false);
    Dijkstra(graf, distance, visited);
    if(distance[n*m-1]==INF) cout<<-1<<"\n";
    else cout<<distance[n*m-1]<<"\n";
}

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