Submission #1094530

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094530		Tesla89	Awesome Arrowland Adventure (eJOI19_adventure)	C++14	0 / 100	4 ms	7340 KiB

adventure

#include <bits/stdc++.h>
#define fi first
#define se second

using namespace std;

struct idk{
    int i,j,w;
};

char mat[501][501];
int d[501][501];
vector<idk>graf[501][501];

bool operator <(const idk &a,const idk &b){
    return a.w<b.w;
}

void dijkstra(int si,int sj){
    set<pair<int,pair<int,int>>>setic;
    setic.insert({si,{sj,0}});
    d[si][sj]=0;
    while(!setic.empty()){
        int i = (*setic.begin()).se.fi;
        int j = (*setic.begin()).se.se;
        setic.erase(setic.begin());
        for(idk v : graf[i][j]){
            if(d[v.i][v.j]>d[i][j]+v.w){
                setic.erase({d[v.i][v.j],{v.i,v.j}});
                d[v.i][v.j]=d[i][j]+v.w;
                setic.insert({d[v.i][v.j],{v.i,v.j}});
            }
        }
    }
}

int calc(char c){
    switch(c){
        case 'N':return 0;
        case 'W':return 1;
        case 'S':return 2;
        case 'E':return 3;
    }
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    for(int i=0;i<501;i++)for(int j=0;j<501;j++)d[i][j]=INT_MAX;
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)cin>>mat[i][j];
        
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(mat[i][j]=='X')continue;
            if(i!=0)graf[i][j].push_back({i-1,j,(calc(mat[i][j])+4)%4});
            if(j!=0)graf[i][j].push_back({i,j-1,(calc(mat[i][j])+3)%4});
            if(i+1!=n)graf[i][j].push_back({i+1,j,(calc(mat[i][j])+2)%4});
            if(j+1!=m)graf[i][j].push_back({i,j+1,(calc(mat[i][j])+1)%4});
        }
    }
    dijkstra(0,0);
    if(d[n-1][m-1]==INT_MAX)cout<<'-1\n';
    else cout<<d[n-1][m-1]<<endl;
    return 0;
}

Compilation message (stderr)

adventure.cpp:65:35: warning: multi-character character constant [-Wmultichar]
   65 |     if(d[n-1][m-1]==INT_MAX)cout<<'-1\n';
      |                                   ^~~~~~
adventure.cpp: In function 'int calc(char)':
adventure.cpp:44:1: warning: control reaches end of non-void function [-Wreturn-type]
   44 | }
      | ^

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