Submission #218292

#	Time	Username	Problem	Language	Result	Execution time	Memory
218292		2fat2code	Awesome Arrowland Adventure (eJOI19_adventure)	C++17	100 / 100	164 ms	42072 KiB

adventure

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define all(a) (a).begin(), (a).end()
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define sz() size()
#define fr first
#define sc second
#define pi pair<int,int>
#define pii pair<pair<int,int>,int>
#define mp make_pair
#define int long long
#define rc(s) return cout<<s,0
#define rcc(s) cout<<s,exit(0)
using namespace std;

const int mod=1e9+7;
const int modp=1999999973;
const int modulo=998244353;

const int nmax=505;

char directii[]={'N','E','S','W','N','E','S','W'};

int n,m;
char c[nmax][nmax];
vector<pair<pair<int,int>,int>>nod[nmax][nmax];

void addedge(int i,int j){
    if(c[i][j]=='X') return;
    int indx=0;
    while(directii[indx]!=c[i][j]) ++indx;
    int cnt=-1;
    for(int t=1;t<=4;t++){
        ++cnt;
        if(directii[indx]=='E' || directii[indx]=='W'){
            if(directii[indx]=='E' && j<m){
                nod[i][j].push_back({{i,j+1},cnt});
            }
            else if(directii[indx]=='W' && j>1){
                nod[i][j].push_back({{i,j-1},cnt});
            }
        }
        else{
            if(directii[indx]=='N' && i>1){
                nod[i][j].push_back({{i-1,j},cnt});
            }
            else if(directii[indx]=='S' && i<n){
                nod[i][j].push_back({{i+1,j},cnt});
            }
        }
        indx++;
    }
}

int viz[nmax][nmax];

int SANDUAUReJOI(){
    int 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:nod[1][1]){
        q.push({it.sc,{it.fr.fr,it.fr.sc}});
    }
    while(q.size() && (q.top().sc.fr!=n || q.top().sc.sc!=m)){
        auto it=q.top();
        int x=it.sc.fr;
        int y=it.sc.sc;
        if(viz[x][y]==1){
            q.pop();
            continue;
        }
        q.pop();
        int z=it.fr;
        for(auto it1 : nod[x][y]){
            if(viz[it1.fr.fr][it1.fr.sc]==0){
                q.push({z+it1.sc,{it1.fr.fr,it1.fr.sc}});
            }
        }
        viz[x][y]=1;
    }
    if(q.empty()==true) return -1LL;
    return q.top().fr;
}


int32_t main(){
  //  ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
    srand(chrono::steady_clock::now().time_since_epoch().count());
    //ifstream cin("input.in");
    cin >> n >> m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin >> c[i][j];
            addedge(i,j);
        }
    }
    cout << SANDUAUReJOI();
}

Compilation message (stderr)

adventure.cpp: In function 'long long int SANDUAUReJOI()':
adventure.cpp:61:9: warning: unused variable 'x' [-Wunused-variable]
     int x=1,y=1;
         ^
adventure.cpp:61:13: warning: unused variable 'y' [-Wunused-variable]
     int x=1,y=1;
             ^

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