Submission #750228

#	Time	Username	Problem	Language	Result	Execution time	Memory
750228		MrM7md	Awesome Arrowland Adventure (eJOI19_adventure)	C++17	0 / 100	1 ms	2260 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[510][510];
int val[510][510];
int dist(int x,int y,int i,int j){
   // if(ch[i][j]=='X')return INT_MAX;
   if(i==x&&j==y)return INT_MAX;
   // cout<<x<<' '<<y<<' '<<i<<' '<<j<<endl;

   if(x==i-1){
      if(ch[x][y]=='E')return 1;
      if(ch[x][y]=='N')return 2;
      if(ch[x][y]=='W')return 3;
      return 0;
   }
   if(x==i+1){
      if(ch[x][y]=='W')return 1;
      if(ch[x][y]=='S')return 2;
      if(ch[x][y]=='E')return 3;
      return 0;
   }if(y==j+1){
      if(ch[x][y]=='S')return 1;
      if(ch[x][y]=='E')return 2;
      if(ch[x][y]=='N')return 3;
      return 0;
   }if(y==j-1){
      if(ch[x][y]=='N')return 1;
      if(ch[x][y]=='W')return 2;
      if(ch[x][y]=='S')return 3;
      return 0;
   }
}
void dijkstra(int x,int y){
   if(ch[x][y]=='X')return ;
   if(val[x-1][y]>(val[x][y]+dist(x,y,x-1,y)) ){
      val[x-1][y]=val[x][y]+dist(x,y,x-1,y);
      dijkstra(x-1,y);
   }
   if(val[x+1][y]>val[x][y]+dist(x,y,x+1,y)){
      val[x+1][y]=val[x][y]+dist(x,y,x+1,y);
      dijkstra(x+1,y);
   }
   if(val[x][y-1]>val[x][y]+dist(x,y,x,y-1)){
      val[x][y-1]=val[x][y]+dist(x,y,x,y-1);
      dijkstra(x,y-1);
   }
   if(val[x][y+1]>val[x][y]+dist(x,y,x,y+1)){
      // cout<<dist(x,y,x,y+1)<<'\n';
      val[x][y+1]=val[x][y]+dist(x,y,x,y+1);
      dijkstra(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=1;i<=m;i++){
      for(int j=1;j<=n;j++){
         val[i][j]=INT_MAX;
         cin >> ch[i][j];
      }
   }
   val[1][1]=0;
   dijkstra(1,1);
   cout<<val[m][n];
}

Compilation message (stderr)

adventure.cpp: In function 'long long int dist(long long int, long long int, long long int, long long int)':
adventure.cpp:42:1: warning: control reaches end of non-void function [-Wreturn-type]
   42 | }
      | ^

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