CSES - Aalto Competitive Programming 2024 - wk9 - Mon - Results
Submission details
Task:Chess board tour
Sender:Nallue
Submission time:2024-11-04 16:54:22 +0200
Language:C++ (C++11)
Status:READY
Result:
Test results
testverdicttime
#1ACCEPTED0.00 sdetails
#2ACCEPTED0.00 sdetails
#30.00 sdetails
#4ACCEPTED0.00 sdetails
#5ACCEPTED0.01 sdetails
#6ACCEPTED0.00 sdetails
#7ACCEPTED0.01 sdetails
#8ACCEPTED0.02 sdetails
#90.00 sdetails
#10ACCEPTED0.00 sdetails
#11--details
#12ACCEPTED0.00 sdetails
#13--details
#14ACCEPTED0.00 sdetails
#150.00 sdetails
#160.00 sdetails
#17--details
#18--details
#19ACCEPTED0.02 sdetails
#20ACCEPTED0.00 sdetails
#21--details
#220.00 sdetails
#23--details
#24ACCEPTED0.00 sdetails
#250.03 sdetails
#260.00 sdetails
#27--details
#28--details
#29--details
#30--details
#31--details
#32--details
#33--details
#34--details
#35--details
#36--details
#37--details
#38--details
#39--details
#40--details
#410.40 sdetails
#42--details
#430.40 sdetails
#44--details
#45--details
#46--details
#470.40 sdetails
#480.40 sdetails
#490.39 sdetails
#500.38 sdetails
#510.40 sdetails
#52--details
#530.40 sdetails
#54--details
#55--details
#56--details

Compiler report

input/code.cpp: In function 'bool isSafe(int, std::vector<std::vector<bool> >, int*, int)':
input/code.cpp:9:9: warning: unused variable 'V' [-Wunused-variable]
    9 |     int V = graph.size();
      |         ^

Code

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


bool isSafe(int v, vector<vector<bool>> graph, 
            int path[], int pos) 
{ 
    int V = graph.size();

    if (graph [path[pos - 1]][ v ] == 0) 
        return false; 

  
    for (int i = 0; i < pos; i++) 
        if (path[i] == v) 
            return false; 

    return true; 
} 

bool hamCycleUtil(vector<vector<bool>> graph, 
                  int path[], int pos) 
{ 
    int V = graph.size();
    if (pos == V) 
    { 
        if (graph[path[pos - 1]][path[0]] == 1) 
            return true; 
        else
            return false; 
    } 
    for (int v = 1; v < V; v++) 
    { 
        if (isSafe(v, graph, path, pos)) 
        { 
            path[pos] = v; 

            if (hamCycleUtil (graph, path, pos + 1) == true) 
                return true; 

            path[pos] = -1; 
        } 
    } 

    return false; 
} 

void printSolution(int path[], int V, int n, int m) 
{  
    int from_x=0;
    int from_y=0;

    for (int i = 1; i <= V; i++){
        int y = path[i] / m; 
        int x = path[i] % m;

        if(y>from_y)cout<<"D";
        else if(y<from_y)cout<<"U";
        else if(x>from_x)cout<<"R";
        else if(x<from_x)cout<<"L";

        from_x = x;
        from_y = y;

    } 


    cout << endl;
} 


bool hamCycle(vector<vector<bool>> graph, int n, int m) 
{ 
    int V = graph.size();
    int *path = new int[V]; 
    for (int i = 0; i < V; i++) 
        path[i] = -1; 

    path[0] = 0; 
    if (hamCycleUtil(graph, path, 1) == false ) 
    { 
        cout << -1 << endl; 
        return false; 
    } 

    printSolution(path, V, n, m); 
    return true; 
} 


int main() 
{ 

    int m,n;

    cin >> n >> m;
    vector<vector<bool>> adj(n*m, vector<bool>(n*m,0));

    
    
    for(int i=0; i<n; i++){
        for(int l=0; l<m; l++){
            if(i-1>=0){
                adj[i*m + l][(i-1)*m +l] = 1;
            }
            if(i+1<n){
                adj[i*m + l][(i+1)*m +l] = 1;
            }
            if(l-1>=0){
                adj[i*m + l][i*m +l-1] = 1;
            }
            if(l+1<m){
                adj[i*m + l][i*m +l+1] = 1;
            }

        }
    }

    hamCycle(adj, n, m); 
    
    return 0; 
} 

Test details

Test 1

Verdict: ACCEPTED

input
2 2

correct output
DRUL

user output
RDLU

Test 2

Verdict: ACCEPTED

input
2 2

correct output
DRUL

user output
RDLU

Test 3

Verdict:

input
2 3

correct output
RRDLLU

user output
RRDLLD

Test 4

Verdict: ACCEPTED

input
2 2

correct output
DRUL

user output
RDLU

Test 5

Verdict: ACCEPTED

input
4 4

correct output
DDDRUURDDRUUULLL

user output
RRRDLLDRRDLLLUUU

Test 6

Verdict: ACCEPTED

input
3 3

correct output
-1

user output
-1

Test 7

Verdict: ACCEPTED

input
4 4

correct output
DDDRUURDDRUUULLL

user output
RRRDLLDRRDLLLUUU

Test 8

Verdict: ACCEPTED

input
3 5

correct output
-1

user output
-1

Test 9

Verdict:

input
3 2

correct output
DDRUUL

user output
RDDLUD

Test 10

Verdict: ACCEPTED

input
4 2

correct output
DDDRUUUL

user output
RDDDLUUU

Test 11

Verdict:

input
5 5

correct output
-1

user output
(empty)

Test 12

Verdict: ACCEPTED

input
2 2

correct output
DRUL

user output
RDLU

Test 13

Verdict:

input
5 5

correct output
-1

user output
(empty)

Test 14

Verdict: ACCEPTED

input
2 2

correct output
DRUL

user output
RDLU

Test 15

Verdict:

input
5 2

correct output
DDDDRUUUUL

user output
RDDDDLUUUD

Test 16

Verdict:

input
2 3

correct output
RRDLLU

user output
RRDLLD

Test 17

Verdict:

input
6 7

correct output
RRRRRRDLLLLLDRRRRRDLLLLLDRRRRR...

user output
(empty)

Test 18

Verdict:

input
5 10

correct output
DDDDRUUURDDDRUUURDDDRUUURDDDRU...

user output
(empty)

Test 19

Verdict: ACCEPTED

input
5 3

correct output
-1

user output
-1

Test 20

Verdict: ACCEPTED

input
6 2

correct output
DDDDDRUUUUUL

user output
RDDDDDLUUUUU

Test 21

Verdict:

input
10 10

correct output
DDDDDDDDDRUUUUUUUURDDDDDDDDRUU...

user output
(empty)

Test 22

Verdict:

input
3 2

correct output
DDRUUL

user output
RDDLUD

Test 23

Verdict:

input
10 10

correct output
DDDDDDDDDRUUUUUUUURDDDDDDDDRUU...

user output
(empty)

Test 24

Verdict: ACCEPTED

input
2 4

correct output
DRRRULLL

user output
RRRDLLLU

Test 25

Verdict:

input
9 2

correct output
DDDDDDDDRUUUUUUUUL

user output
RDDDDDDDDLUUUUUUUD

Test 26

Verdict:

input
2 5

correct output
RRRRDLLLLU

user output
RRRRDLLLLD

Test 27

Verdict:

input
56 60

correct output
DDDDDDDDDDDDDDDDDDDDDDDDDDDDDD...

user output
(empty)

Test 28

Verdict:

input
43 100

correct output
DDDDDDDDDDDDDDDDDDDDDDDDDDDDDD...

user output
(empty)

Test 29

Verdict:

input
45 20

correct output
DDDDDDDDDDDDDDDDDDDDDDDDDDDDDD...

user output
(empty)

Test 30

Verdict:

input
56 9

correct output
RRRRRRRRDLLLLLLLDRRRRRRRDLLLLL...

user output
(empty)

Test 31

Verdict:

input
97 91

correct output
-1

user output
(empty)

Test 32

Verdict:

input
23 7

correct output
-1

user output
(empty)

Test 33

Verdict:

input
90 95

correct output
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRR...

user output
(empty)

Test 34

Verdict:

input
9 24

correct output
DDDDDDDDRUUUUUUURDDDDDDDRUUUUU...

user output
(empty)

Test 35

Verdict:

input
88 3

correct output
RRDLDRDLDRDLDRDLDRDLDRDLDRDLDR...

user output
(empty)

Test 36

Verdict:

input
3 38

correct output
DDRURDRURDRURDRURDRURDRURDRURD...

user output
(empty)

Test 37

Verdict:

input
111 119

correct output
-1

user output
(empty)

Test 38

Verdict:

input
84 200

correct output
DDDDDDDDDDDDDDDDDDDDDDDDDDDDDD...

user output
(empty)

Test 39

Verdict:

input
88 38

correct output
DDDDDDDDDDDDDDDDDDDDDDDDDDDDDD...

user output
(empty)

Test 40

Verdict:

input
111 16

correct output
DDDDDDDDDDDDDDDDDDDDDDDDDDDDDD...

user output
(empty)

Test 41

Verdict:

input
194 181

correct output
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRR...

user output
(empty)

Test 42

Verdict:

input
46 12

correct output
DDDDDDDDDDDDDDDDDDDDDDDDDDDDDD...

user output
(empty)

Test 43

Verdict:

input
179 190

correct output
DDDDDDDDDDDDDDDDDDDDDDDDDDDDDD...

user output
(empty)

Test 44

Verdict:

input
17 47

correct output
-1

user output
(empty)

Test 45

Verdict:

input
175 4

correct output
DDDDDDDDDDDDDDDDDDDDDDDDDDDDDD...

user output
(empty)

Test 46

Verdict:

input
4 74

correct output
DDDRUURDDRUURDDRUURDDRUURDDRUU...

user output
(empty)

Test 47

Verdict:

input
550 594

correct output
DDDDDDDDDDDDDDDDDDDDDDDDDDDDDD...

user output
(empty)

Test 48

Verdict:

input
418 998

correct output
DDDDDDDDDDDDDDDDDDDDDDDDDDDDDD...

user output
(empty)

Test 49

Verdict:

input
437 186

correct output
DDDDDDDDDDDDDDDDDDDDDDDDDDDDDD...

user output
(empty)

Test 50

Verdict:

input
552 72

correct output
DDDDDDDDDDDDDDDDDDDDDDDDDDDDDD...

user output
(empty)

Test 51

Verdict:

input
968 901

correct output
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRR...

user output
(empty)

Test 52

Verdict:

input
223 57

correct output
-1

user output
(empty)

Test 53

Verdict:

input
893 948

correct output
DDDDDDDDDDDDDDDDDDDDDDDDDDDDDD...

user output
(empty)

Test 54

Verdict:

input
78 229

correct output
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRR...

user output
(empty)

Test 55

Verdict:

input
874 13

correct output
RRRRRRRRRRRRDLLLLLLLLLLLDRRRRR...

user output
(empty)

Test 56

Verdict:

input
12 366

correct output
DDDDDDDDDDDRUUUUUUUUUURDDDDDDD...

user output
(empty)