Submission #960619

#	Time	Username	Problem	Language	Result	Execution time	Memory
960619		inesfi	Awesome Arrowland Adventure (eJOI19_adventure)	C++14	100 / 100	41 ms	16480 KiB

adventure

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define endl "\n"

const int TAILLEMAXI=502;
int nblignes,nbcolonnes,taille,ielement,lig,col,direc,deja;
char carac;
int grille[TAILLEMAXI][TAILLEMAXI];
int dejavu[TAILLEMAXI][TAILLEMAXI][4];
deque<tuple<int,int,int>> encours;

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>nblignes>>nbcolonnes;
    for (int ilig=0;ilig<nbcolonnes;ilig++){
        for (int icol=0;icol<nbcolonnes;icol++){
            cin>>carac;
            if (carac=='X'){
                grille[ilig][icol]=-1;
            }
            else if (carac=='E'){
                grille[ilig][icol]=1;
            }
            else if (carac=='S'){
                grille[ilig][icol]=2;
            }
            else if (carac=='W'){
                grille[ilig][icol]=3;
            }
        }
    }
    if (grille[0][0]=='X'){
        cout<<-1<<endl;
        return 0;
    }
    encours.push_back(make_tuple(0,0,grille[0][0]));
    while ((int)encours.size()!=0){
        taille=encours.size();
        ielement=0;
        while (ielement<taille){
            lig=get<0>(encours.front());
            col=get<1>(encours.front());
            direc=get<2>(encours.front());
            encours.pop_front();
            if (lig==nblignes-1 and col==nbcolonnes-1){
                cout<<deja<<endl;
                return 0;
            }
            if (direc>=0 and lig>=0 and col>=0 and lig<nblignes and col<nbcolonnes and dejavu[lig][col][direc]==0 and grille[lig][col]!=-1){
                dejavu[lig][col][direc]=1;
                ielement--;
                if (direc==0){
                    encours.push_front(make_tuple(lig-1,col,grille[lig-1][col]));
                    encours.push_back(make_tuple(lig,col,1));
                }
                else if (direc==1){
                    encours.push_front(make_tuple(lig,col+1,grille[lig][col+1]));
                    encours.push_back(make_tuple(lig,col,2));
                }
                else if (direc==2){
                    encours.push_front(make_tuple(lig+1,col,grille[lig+1][col]));
                    encours.push_back(make_tuple(lig,col,3));
                }
                else {
                    encours.push_front(make_tuple(lig,col-1,grille[lig][col-1]));
                    encours.push_back(make_tuple(lig,col,0));
                }
            }
            ielement++;
        }
        deja++;
    }
    cout<<-1<<endl;
    return 0;
}

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