oj.uz

Submission #218541

# Submission time Handle Problem Language Result Execution time Memory
218541 2020-04-02T09:14:33 Z Sho10 Awesome Arrowland Adventure (eJOI19_adventure) C++14
0 / 100
 10 ms 6400 KB 
/*
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(mp(mp(i,j+1),cnt));
            }else if(directii[pos]=='W'&&j>1){
            v[i][j].pb(mp(mp(i,j-1),cnt));
            }
}else {
if(directii[pos]=='N'&&i>1){
        v[i][j].pb(mp(mp(i-1,j),cnt));
}else if(directii[pos]=='S'&&i<n){
v[i][j].pb(mp(mp(i+1,j),cnt));
}
}
pos++;
}
}
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);
}
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.size()==0){
       rc("-1");
      }else {
          cout<<q.top().f;
          return 0;
      }
}
}

Compilation message

adventure.cpp: In function 'int32_t main()':
adventure.cpp:64:4: warning: unused variable 'x' [-Wunused-variable]
 ll x=1,y=1;
    ^
adventure.cpp:64:8: warning: unused variable 'y' [-Wunused-variable]
 ll x=1,y=1;
        ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 6400 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 6400 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 6400 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 6400 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 6400 KB Output isn't correct
2 Halted 0 ms 0 KB -