Submission #232206

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

adventure

#include <bits/stdc++.h>

#define mp(a,b) make_pair(a,b)

using namespace std;


struct ano{

int c;
int d;

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

};

vector<pair<int,int> > a[250000];
priority_queue<pair<int,int> > q;
int d[250000];

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

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



int i,j;
char c;

for(i=0;i<n*m;i++)
    d[i]=1000000;

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

    cin>>c;

    if(c=='X')
        continue;

    if(c=='N'){
        if(i-1>=0)
            a[i*m+j].push_back(mp(0,(i-1)*m+j));
        if(j+1<m)
            a[i*m+j].push_back(mp(1,i*m+j+1));
        if(i+1<n)
            a[i*m+j].push_back(mp(2,(i+1)*m+j));
        if(j-1>=0)
            a[i*m+j].push_back(mp(3,i*m+j-1));
    }
    else if(c=='E'){
        if(i-1>=0)
            a[i*m+j].push_back(mp(3,(i-1)*m+j));
        if(j+1<m)
            a[i*m+j].push_back(mp(0,i*m+j+1));
        if(i+1<n)
            a[i*m+j].push_back(mp(1,(i+1)*m+j));
        if(j-1>=0)
            a[i*m+j].push_back(mp(2,i*m+j-1));
    }
    else if(c=='S'){
        if(i-1>=0)
            a[i*m+j].push_back(mp(2,(i-1)*m+j));
        if(j+1<m)
            a[i*m+j].push_back(mp(3,i*m+j+1));
        if(i+1<n)
            a[i*m+j].push_back(mp(0,(i+1)*m+j));
        if(j-1>=0)
            a[i*m+j].push_back(mp(1,i*m+j-1));
    }
    else{
        if(i-1>=0)
            a[i*m+j].push_back(mp(1,(i-1)*m+j));
        if(j+1<m)
            a[i*m+j].push_back(mp(2,i*m+j+1));
        if(i+1<n)
            a[i*m+j].push_back(mp(3,(i+1)*m+j));
        if(j-1>=0)
            a[i*m+j].push_back(mp(0,i*m+j-1));
    }

}

q.push({0,0});
d[0]=0;

int start,w;

while(!q.empty()){
    start=q.top().second;
    w=q.top().first;
    q.pop();

    if(d[start]<w)
        continue;

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

}

if(d[n*m-1]==1000000)
    cout<<-1<<'\n';
else
    cout<<d[n*m-1]<<'\n';


}

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