Submission #218553

#	Time	Username	Problem	Language	Result	Execution time	Memory
218553		Sho10	Awesome Arrowland Adventure (eJOI19_adventure)	C++14	100 / 100	141 ms	39140 KiB

adventure

/*
ID: Sho10
LANG: C++
*/
#include <bits/stdc++.h> //Andrei Alexandru a.k.a Sho10
#define ll long long int
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define all(a) (a).begin(), (a).end()
#define sz size
#define f first
#define s second
#define pb push_back
#define er erase
#define in insert
#define mp make_pair
#define pi pair
#define rc(s) return cout<<s,0
#define endl '\n'
#define mod 1000000007
#define PI 3.14159265359
#define CODE_START  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
ll n,m;
char c[505][505];
vector<pair<pair<ll,ll>,ll>>v[505][505];
ll viz[505][505];
char directii[]={'N','E','S','W','N','E','S','W'};
void edge(ll i,ll j){
if(c[i][j]=='X'){
    return;
}
ll pos=0;
while(directii[pos]!=c[i][j]) ++pos;
ll cnt=-1;
for(ll t=1;t<=4;t++)
{
    ++cnt;
    if(directii[pos]=='E'||directii[pos]=='W'){
            if(directii[pos]=='E'&&j<m){
                v[i][j].pb({{i,j+1},cnt});
            }else if(directii[pos]=='W'&&j>1){
            v[i][j].pb({{i,j-1},cnt});
            }
}else {
if(directii[pos]=='N'&&i>1){
        v[i][j].pb({{i-1,j},cnt});
}else if(directii[pos]=='S'&&i<n){
v[i][j].pb({{i+1,j},cnt});
}
}
pos++;
}
}
ll sol(){
ll x=1,y=1;
viz[1][1]=1;
priority_queue<pair<int,pair<int,int>>,vector<pair<int,pair<int,int>>>,greater<pair<int,pair<int,int>>>>q;
for(auto it:v[1][1]){
    q.push({it.s,{it.f.f,it.f.s}});
}
while(q.size()&&(q.top().s.f!=n || q.top().s.s!=m)){
      auto it=q.top();
      ll x=it.s.f;
      ll y=it.s.s;
      if(viz[x][y]==1){
        q.pop();
        continue;
      }
      q.pop();
      ll val=it.f;
      for(auto it1:v[x][y]){
        if(viz[it1.f.f][it1.f.s]==0){
            q.push({val+it1.s,{it1.f.f,it1.f.s}});
        }
      }
       viz[x][y]=1;
}
if(q.empty()==true){
       return -1;
      }
          return q.top().f;
}
int32_t main(){
CODE_START;
cin>>n>>m;
for(ll i=1;i<=n;i++)
    for(ll j=1;j<=m;j++)
{
    cin>>c[i][j];
    edge(i,j);
}
cout<<sol();
}

Compilation message (stderr)

adventure.cpp: In function 'long long int sol()':
adventure.cpp:56:4: warning: unused variable 'x' [-Wunused-variable]
 ll x=1,y=1;
    ^
adventure.cpp:56:8: warning: unused variable 'y' [-Wunused-variable]
 ll x=1,y=1;
        ^

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