Submission #465096

#	Time	Username	Problem	Language	Result	Execution time	Memory
465096		oscar1f	Awesome Arrowland Adventure (eJOI19_adventure)	C++17	100 / 100	83 ms	8448 KiB

adventure

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

const int MAX_TAILLE=500;
int nbLig,nbCol,dist,longueur,lig,col,direc;
int grille[MAX_TAILLE][MAX_TAILLE],dv[MAX_TAILLE][MAX_TAILLE][4];
deque<tuple<int,int,int>> aTraiter;
tuple<int,int,int> temp;
char carac;

int main() {
   ios_base::sync_with_stdio(false);
   cin>>nbLig>>nbCol;
   for (int i=0;i<nbLig;i++) {
      for (int j=0;j<nbCol;j++) {
         cin>>carac;
         if (carac=='X') {
            grille[i][j]=-1;
         }
         if (carac=='N') {
            grille[i][j]=0;
         }
         if (carac=='E') {
            grille[i][j]=1;
         }
         if (carac=='S') {
            grille[i][j]=2;
         }
         if (carac=='W') {
            grille[i][j]=3;
         }
      }
   }
   aTraiter.push_back(make_tuple(0,0,grille[0][0]));
   while (aTraiter.size()>0) {
      longueur=aTraiter.size();
      for (int i=0;i<longueur;i++) {
         temp=aTraiter.front();
         aTraiter.pop_front();
         lig=get<0>(temp);
         col=get<1>(temp);
         direc=get<2>(temp);
         if (lig==nbLig-1 and col==nbCol-1) {
            cout<<dist<<endl;
            return 0;
         }
         if (lig>=0 and lig<nbLig and col>=0 and col<nbCol and grille[lig][col]!=-1 and dv[lig][col][direc]==0) {
            dv[lig][col][direc]=1;
            aTraiter.push_back(make_tuple(lig,col,(direc+1)%4));
            longueur++;
            if (direc==0) {
               aTraiter.push_front(make_tuple(lig-1,col,grille[lig-1][col]));
            }
            if (direc==1) {
               aTraiter.push_front(make_tuple(lig,col+1,grille[lig][col+1]));
            }
            if (direc==2) {
               aTraiter.push_front(make_tuple(lig+1,col,grille[lig+1][col]));
            }
            if (direc==3) {
               aTraiter.push_front(make_tuple(lig,col-1,grille[lig][col-1]));
            }
         }
      }
      dist++;
   }
   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