Submission #232160

#	Time	Username	Problem	Language	Result	Execution time	Memory
232160		Dremix10	Awesome Arrowland Adventure (eJOI19_adventure)	C++17	50 / 100	2086 ms	50812 KiB

adventure

#include <bits/stdc++.h>
using namespace std;

struct ano{

int c;
int d;

bool operator<(const ano &o)const{
return d>o.d;
}

};


int main (){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

int n,m;
cin>>n>>m;

vector<vector<ano> > a(n*m,vector<ano>());
int arr[n][m];
int i,j;
//int cnt=0;

for(i=0;i<n;i++)
for(j=0;j<m;j++){
    char c;
    cin>>c;

    if(c=='X')
        arr[i][j]=-1;
    else if(c=='N')
        arr[i][j]=0;
    else if(c=='E')
        arr[i][j]=1;
    else if(c=='S')
        arr[i][j]=2;
    else
        arr[i][j]=3;

}
for(i=0;i<n;i++)
for(j=0;j<m;j++){

    if(arr[i][j]==-1)
        continue;

    if(arr[i][j]==0){
        if(i-1>=0)
            a[i*m+j].push_back({(i-1)*m+j,0});
        if(j+1<m)
            a[i*m+j].push_back({i*m+j+1,1});
        if(i+1<n)
            a[i*m+j].push_back({(i+1)*m+j,2});
        if(j-1>=0)
            a[i*m+j].push_back({i*m+j-1,3});
    }
    else if(arr[i][j]==1){
        if(i-1>=0)
            a[i*m+j].push_back({(i-1)*m+j,3});
        if(j+1<m)
            a[i*m+j].push_back({i*m+j+1,0});
        if(i+1<n)
            a[i*m+j].push_back({(i+1)*m+j,1});
        if(j-1>=0)
            a[i*m+j].push_back({i*m+j-1,2});
    }
    else if(arr[i][j]==2){
        if(i-1>=0)
            a[i*m+j].push_back({(i-1)*m+j,2});
        if(j+1<m)
            a[i*m+j].push_back({i*m+j+1,3});
        if(i+1<n)
            a[i*m+j].push_back({(i+1)*m+j,0});
        if(j-1>=0)
            a[i*m+j].push_back({i*m+j-1,1});
    }
    else{
        if(i-1>=0)
            a[i*m+j].push_back({(i-1)*m+j,1});
        if(j+1<m)
            a[i*m+j].push_back({i*m+j+1,2});
        if(i+1<n)
            a[i*m+j].push_back({(i+1)*m+j,3});
        if(j-1>=0)
            a[i*m+j].push_back({i*m+j-1,0});
    }

}
/*
for(i=0;i<n*m;i++){
    cout<<i<<" -> ";
    for(j=0;j<a[i].size();j++)
    cout<<a[i][j].c<<" - "<<a[i][j].d<<"  ";
cout<<endl;
}
*/

priority_queue<ano> q;
vector <int> d(n*m,10000000);
q.push({0,0});
d[0]=0;

while(!q.empty()){
    int start=q.top().c;
    int w=q.top().d;
    q.pop();
    //cout<<start<<endl;
    if(d[start]<w)
        continue;

    for(auto x : a[start])
    if(d[x.c]>d[start]+x.d){
        d[x.c]=d[start]+x.d;
        q.push(x);
    }

}

if(d[n*m-1]==10000000)
    cout<<-1<<endl;
else
    cout<<d[n*m-1]<<endl;


}

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