Submission #286486

#	Time	Username	Problem	Language	Result	Execution time	Memory
286486		wildturtle	Awesome Arrowland Adventure (eJOI19_adventure)	C++14	100 / 100	152 ms	38248 KiB

adventure

#include<bits/stdc++.h>
using namespace std;
long long a,b,c,d,i,e,f,g,n,m,k,l,A[500005];
string s[505];
vector < pair < long long , long long > > v[500005];
priority_queue< pair < long long , long long > > pq;
int main() {
    cin>>n>>m;
    for(long long i=1;i<=n;i++) {
        cin>>s[i];
        
        s[i]='#'+s[i];
      // cout<<s[i]<<endl;
    }
    //cout<<s[2][1]<<endl;
    for(long long i=1;i<=n;i++) {
        for(long long j=1;j<=m;j++) {
            if(s[i][j]=='X') continue;
            a=0;
            if(i-1>0) {
                if(s[i][j]=='N') a=0;
                else if(s[i][j]=='E') a=3;
                else if(s[i][j]=='W') a=1;
                else a=2;
                v[(i-1)*m+j].push_back({(i-2)*m+j,a});
            }
            a=0;
            if(i+1<=n) {
                if(s[i][j]=='S') a=0;
                else if(s[i][j]=='W') a=3;
                else if(s[i][j]=='E') a=1;
                else a=2;
                v[(i-1)*m+j].push_back({i*m+j,a});                
            }
            a=0;
            if(j-1>0) {
                if(s[i][j]=='W') a=0;
                else if(s[i][j]=='N') a=3;
                else if(s[i][j]=='S') a=1;
                else if(s[i][j]=='E') a=2;
                v[(i-1)*m+j].push_back({(i-1)*m+j-1,a});
            }
            a=0;
            if(j+1<=m) {
                if(s[i][j]=='E') a=0;
                else if(s[i][j]=='S') a=3;
                else if(s[i][j]=='N') a=1;
                else if(s[i][j]=='W') a=2;
                //if((i-1)*m+j==4) cout<<a<<" "<<s[i][j]<<" "<<i<<" "<<j<<" "<<s[i]<<endl;
                v[(i-1)*m+j].push_back({(i-1)*m+j+1,a});                
            }
        }
    }
    for(long long i=1;i<=n*m;i++)
        A[i]=100000000001ll;
    /*for(long long i=0;i<v[4].size();i++)
        cout<<v[4][i].first<<" "<<v[4][i].second<<endl;
        cout<<endl;*/
    A[1]=0;
    pq.push({0,1});
    while (pq.size()>0) {
        a=-(pq.top().first);
        b=pq.top().second;
        pq.pop();
        for(long long i=0;i<v[b].size();i++) {
            c=v[b][i].first; d=v[b][i].second;
            if(A[c]>A[b]+d) { A[c]=A[b]+d; pq.push({-(A[c]), c}); }
        }
    }
    /*for(long long i=1;i<=n*m;i++) {
        cout<<A[i]<<" ";
        if(i%m==0) cout<<endl;
    }*/
    if(A[n*m]==100000000001) cout<<-1;
    else cout<<A[n*m];
}

Compilation message (stderr)

adventure.cpp: In function 'int main()':
adventure.cpp:65:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |         for(long long i=0;i<v[b].size();i++) {
      |                           ~^~~~~~~~~~~~

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