oj.uz

Submission #960619

# Submission time Handle Problem Language Result Execution time Memory
960619 2024-04-10T17:24:16 Z inesfi Awesome Arrowland Adventure (eJOI19_adventure) C++14
100 / 100
 41 ms 16480 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3164 KB Output is correct
2 Correct 1 ms 2908 KB Output is correct
3 Correct 1 ms 2908 KB Output is correct
4 Correct 2 ms 3536 KB Output is correct
5 Correct 2 ms 3420 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 2 ms 3164 KB Output is correct
9 Correct 2 ms 3676 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3164 KB Output is correct
2 Correct 1 ms 2908 KB Output is correct
3 Correct 1 ms 2908 KB Output is correct
4 Correct 2 ms 3536 KB Output is correct
5 Correct 2 ms 3420 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 2 ms 3164 KB Output is correct
9 Correct 2 ms 3676 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 3164 KB Output is correct
13 Correct 2 ms 3932 KB Output is correct
14 Correct 0 ms 2396 KB Output is correct
15 Correct 1 ms 2652 KB Output is correct
16 Correct 2 ms 3420 KB Output is correct
17 Correct 2 ms 3420 KB Output is correct
18 Correct 1 ms 2456 KB Output is correct
19 Correct 1 ms 2396 KB Output is correct
20 Correct 2 ms 3792 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3932 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 3 ms 3676 KB Output is correct
6 Correct 3 ms 3676 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct

Subtask #5
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3164 KB Output is correct
2 Correct 1 ms 2908 KB Output is correct
3 Correct 1 ms 2908 KB Output is correct
4 Correct 2 ms 3536 KB Output is correct
5 Correct 2 ms 3420 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 2 ms 3164 KB Output is correct
9 Correct 2 ms 3676 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 3164 KB Output is correct
13 Correct 2 ms 3932 KB Output is correct
14 Correct 0 ms 2396 KB Output is correct
15 Correct 1 ms 2652 KB Output is correct
16 Correct 2 ms 3420 KB Output is correct
17 Correct 2 ms 3420 KB Output is correct
18 Correct 1 ms 2456 KB Output is correct
19 Correct 1 ms 2396 KB Output is correct
20 Correct 2 ms 3792 KB Output is correct
21 Correct 1 ms 2396 KB Output is correct
22 Correct 1 ms 2396 KB Output is correct
23 Correct 1 ms 2396 KB Output is correct
24 Correct 1 ms 2396 KB Output is correct
25 Correct 2 ms 3932 KB Output is correct
26 Correct 1 ms 2392 KB Output is correct
27 Correct 1 ms 2652 KB Output is correct
28 Correct 1 ms 2652 KB Output is correct
29 Correct 3 ms 3676 KB Output is correct
30 Correct 3 ms 3676 KB Output is correct
31 Correct 1 ms 2652 KB Output is correct
32 Correct 1 ms 2396 KB Output is correct
33 Correct 1 ms 2396 KB Output is correct
34 Correct 1 ms 2396 KB Output is correct
35 Correct 6 ms 4444 KB Output is correct
36 Correct 1 ms 3164 KB Output is correct
37 Correct 5 ms 4188 KB Output is correct
38 Correct 1 ms 2648 KB Output is correct
39 Correct 41 ms 10488 KB Output is correct
40 Correct 40 ms 10580 KB Output is correct
41 Correct 8 ms 4196 KB Output is correct
42 Correct 39 ms 10612 KB Output is correct
43 Correct 13 ms 16480 KB Output is correct
44 Correct 6 ms 4160 KB Output is correct