Submission #750276

#	Time	Username	Problem	Language	Result	Execution time	Memory
750276		MrM7md	Awesome Arrowland Adventure (eJOI19_adventure)	C++17	34 / 100	2 ms	1492 KiB

adventure

#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define endl '\n'
#define F first
#define S second
#define pb push_back
#define all(a) a.begin(),a.end()
const int N=1e6+500;
const int off=(1<<18);
const int MOD = 1e9+7;

char ch[502][502];
int val[502][502];
map<pair<int,int>,int>vis;
void dijkstra(int a,int b){
   priority_queue<pair<int,pair<int,int>>>pq;
   vis[{a,b}]=1;
   pq.push({0,{a,b}});
   while(!pq.empty()){
      int x=pq.top().S.F,y=pq.top().S.S;
      int vl=pq.top().F;
      pq.pop();
      vis[{x,y}]=1;
      // cout<<x<<' '<<y<<endl;
      if(ch[x][y]=='X')continue ;
      int l=INT_MAX,r=INT_MAX,u=INT_MAX,d=INT_MAX;

      if(ch[x][y]=='E')r=0,l=2,u=3,d=1;
      if(ch[x][y]=='N')r=1,l=3,u=0,d=2;
      if(ch[x][y]=='W')r=2,l=0,u=1,d=3;
      if(ch[x][y]=='S')r=3,l=1,u=2,d=0;

      vector<pair<int,pair<int,int>>>v;
      if(val[x-1][y]>(val[x][y]+u) ){
         val[x-1][y]=val[x][y]+u;
         if(ch[x-1][y]!='X'&&!vis[{x-1,y}]){
            vis[{x-1,y}]=1;
            pq.push({val[x-1][y]*-1,{x-1,y}});
         }
      }
      // if(x==1&&y==4)cout<<d<<' '<<ch[x][y]<<' '<<val[1][3]<<endl;
      if(val[x+1][y]>(val[x][y]+d) ){
         val[x+1][y]=val[x][y]+d;
         if(ch[x+1][y]!='X'&&!vis[{x+1,y}]){
            vis[{x+1,y}]=1;
            pq.push({val[x+1][y]*-1,{x+1,y}});
         }
      }
      if(val[x][y-1]>(val[x][y]+l) ){
         val[x][y-1]=val[x][y]+l;
         if(ch[x][y-1]!='X'&&!vis[{x,y-1}]){
            vis[{x,y-1}]=1;
            pq.push({val[x][y-1]*-1,{x,y-1}});
         }
      }
      if(val[x][y+1]>(val[x][y]+r) ){
         // cout<<dist(x,y,x,y+1)<<'\n';
         val[x][y+1]=val[x][y]+r;
         if(ch[x][y+1]!='X'&&!vis[{x,y+1}]){
            vis[{x,y+1}]=1;
            pq.push({val[x][y+1]*-1,{x,y+1}});
         }
      }

   }
}
signed main(){
   ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
   int n,m;
   cin >> m >> n;
   // memset(val,-1,sizeof(val));
   for(int i=0;i<=501;i++){
      for(int j=0;j<=501;j++){
         ch[i][j]='X';
         val[i][j]=-1;
      }
   }
   for(int i=1;i<=m;i++){
      for(int j=1;j<=n;j++){
         val[i][j]=1e9;
         cin >> ch[i][j];
      }
   }
   val[1][1]=0;
   dijkstra(1,1);
   if(val[m][n]==1e9)val[m][n]=-1;
   cout<<val[m][n];
}

Compilation message (stderr)

adventure.cpp: In function 'void dijkstra(int, int)':
adventure.cpp:22:11: warning: unused variable 'vl' [-Wunused-variable]
   22 |       int vl=pq.top().F;
      |           ^~

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