Submission #525679

#	Time	Username	Problem	Language	Result	Execution time	Memory
525679		ammar2000	Awesome Arrowland Adventure (eJOI19_adventure)	C++17	100 / 100	82 ms	11036 KiB

adventure

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define F first
#define S second
#define coy cout<<"YES\n"
#define con cout<<"NO\n"
#define co1 cout<<"-1\n"
#define sc(x) scanf("%lld",&x)
#define all(x) x.begin(),x.end()
#define fast ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
const int SI=3e5+7;
ll INF=8e18+7;
int dx[] = {1 , -1 , 0 , 0};
int dy[] = {0 , 0 , 1 , -1};
int MOD=1e9+7;
ll n,m ,vis[555][555],ans[555][555];
map <char,ll> mp[4];
char c[555][555];
priority_queue< pair<ll,pair < ll,ll> > > pq;
int main()
{
   fast
   mp[0]['N']=0,mp[1]['N']=1, mp[2]['N']=2,mp[3]['N']=3;
   mp[0]['E']=3,mp[1]['E']=0, mp[2]['E']=1,mp[3]['E']=2;
   mp[0]['S']=2,mp[1]['S']=3, mp[2]['S']=0,mp[3]['S']=1;
   mp[0]['W']=1,mp[1]['W']=2, mp[2]['W']=3,mp[3]['W']=0;
   cin>>m>>n;
   for (int i=0;i<m;i++)
    for (int u=0;u<n;u++)
      cin>>c[i][u];
   for (int i=0;i<=m;i++)
    for (int u=0;u<=n;u++)
       ans[i][u]=-INF;
   ans[0][0]=0;
   pq.push({0,{0,0}});
   while (pq.size())
   {
       ll d=pq.top().F,x=pq.top().S.F,y=pq.top().S.S;
       pq.pop();
       if (vis[x][y]||c[x][y]=='X')
        continue;
        vis[x][y]=1;
       if (x>0&&ans[x-1][y]<d-mp[0][c[x][y]])
       ans[x-1][y]=d-mp[0][c[x][y]],pq.push({ans[x-1][y],{x-1,y}});
       if (y>0&&ans[x][y-1]<d-mp[3][c[x][y]])
       ans[x][y-1]=d-mp[3][c[x][y]],pq.push({ans[x][y-1],{x,y-1}});
       if (x<m-1&&ans[x+1][y]<d-mp[2][c[x][y]])
       ans[x+1][y]=d-mp[2][c[x][y]],pq.push({ans[x+1][y],{x+1,y}});
       if (y<n-1&&ans[x][y+1]<d-mp[1][c[x][y]])
        ans[x][y+1]=d-mp[1][c[x][y]],pq.push({ans[x][y+1],{x,y+1}});
   }
   if (ans[m-1][n-1]==-INF)
    co1;
   else cout <<-ans[m-1][n-1];
   // use scanf not cin
   return 0;
}

Compilation message (stderr)

adventure.cpp: In function 'int main()':
adventure.cpp:42:8: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   42 |        if (vis[x][y]||c[x][y]=='X')
      |        ^~
adventure.cpp:44:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   44 |         vis[x][y]=1;
      |         ^~~

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