Submission #882093

#	Time	Username	Problem	Language	Result	Execution time	Memory
882093		spetar76	Awesome Arrowland Adventure (eJOI19_adventure)	C++17	100 / 100	78 ms	22472 KiB

adventure

#include <bits/stdc++.h>

using namespace std;
#define maxn 250052
int v,n,m,e;
int ind(int i, int j)
{
    return (i-1)*n+j;
}
vector<pair<int,int>> adj[maxn];
int dist[maxn];
bool pos[maxn];
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> q;

void dijkstra(int pocetan)
{
    //dist[pocetan]=0;
    for (int i=0; i<=n*m; ++i){
        dist[i]=-1;
    }
    q.push(make_pair(0, pocetan));
    while (!q.empty()){
        pair<int,int> x=q.top();
        q.pop();
        if (!pos[x.second]){
            dist[x.second]=x.first;
            pos[x.second]=true;
            for (auto i:adj[x.second]){
                if (!pos[i.first]){
                    q.push(make_pair(x.first + i.second, i.first));
                }
            }
        }

    }
    return;
}

int main()
{
    cin>>m>>n;
    int a[m+1][n+1];
    for (int i=1; i<=m; ++i){
        string st;
        cin>>st;
        for (int j=0; j<n; ++j){
            if (st[j]=='X'){a[i][j+1]=-1;}
            else if (st[j]=='E'){a[i][j+1]=0;}
            else if (st[j]=='S'){a[i][j+1]=1;}
            else if (st[j]=='W'){a[i][j+1]=2;}
            else{a[i][j+1]=3;}
        }
    }

    for (int i=1; i<=m; ++i){
        for (int j=1; j<=n; ++j){
            if (j<n && a[i][j]>=0){
                adj[ind(i,j)].push_back(make_pair(ind(i,j+1), (4-a[i][j])%4));
            }
            if (j>1 && a[i][j]>=0){
                adj[ind(i,j)].push_back(make_pair(ind(i,j-1), (6-a[i][j])%4));
            }
            if (i>1 && a[i][j]>=0){
                adj[ind(i,j)].push_back(make_pair(ind(i-1,j), (7-a[i][j])%4));
            }
            if (i<m && a[i][j]>=0){
                adj[ind(i,j)].push_back(make_pair(ind(i+1,j), (5-a[i][j])%4));
            }
        }
    }
    dijkstra(1);
    cout<<dist[m*n];
    return 0;
}

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