Chess board tour

input/code.cpp: In function 'bool isSafe(int, const std::vector<std::vector<bool> >&, int*, Bitmask, int)':
input/code.cpp:10:9: warning: unused variable 'V' [-Wunused-variable]
   10 |     int V = graph.size();
      |         ^
input/code.cpp: In function 'int countUnvisitedNeighbors(int, const std::vector<std::vector<bool> >&, Bitmask)':
input/code.cpp:16:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |     for (int i = 0; i < graph.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~
input/code.cpp: In function 'bool hamCycleUtil(std::vector<std::vector<bool> >&, int*, Bitmask, int)':
input/code.cpp:36:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   36 |     for (auto [_, v] : neighbors) {
      |               ^

#include <iostream>
#include <vector>
#include <algorithm>
#include <bitset>
using namespace std;

typedef bitset<100> Bitmask;

bool isSafe(int v, const vector<vector<bool>>& graph, int path[], Bitmask visited, int pos) {
    int V = graph.size();
    return graph[path[pos - 1]][v] && !visited[v];
}

int countUnvisitedNeighbors(int v, const vector<vector<bool>>& graph, Bitmask visited) {
    int count = 0;
    for (int i = 0; i < graph.size(); i++) {
        if (graph[v][i] && !visited[i]) count++;
    }
    return count;
}

bool hamCycleUtil(vector<vector<bool>>& graph, int path[], Bitmask visited, int pos) {
    int V = graph.size();
    if (pos == V) {
        return graph[path[pos - 1]][path[0]];
    }

    vector<pair<int, int>> neighbors;
    for (int v = 1; v < V; v++) {
        if (isSafe(v, graph, path, visited, pos)) {
            neighbors.push_back({countUnvisitedNeighbors(v, graph, visited), v});
        }
    }
    sort(neighbors.begin(), neighbors.end());

    for (auto [_, v] : neighbors) {
        path[pos] = v;
        visited[v] = true;

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

        path[pos] = -1;
        visited[v] = false;
    }

    return false;
}

void printSolution(int path[], int V, int n, int m) {
    int from_x = 0, 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;
    }
    if(from_y<0)cout<<"D";
    else if(from_y>0)cout<<"U";
    else if(from_x<0)cout<<"R";
    else if(from_x>0)cout<<"L";
    cout << endl;
}

bool hamCycle(vector<vector<bool>>& graph, int n, int m) {
    int V = graph.size();
    int path[V];
    Bitmask visited;

    for (int i = 0; i < V; i++) path[i] = -1;
    path[0] = 0;
    visited[0] = true;

    if (!hamCycleUtil(graph, path, visited, 1)) {
        cout << -1 << endl;
        return false;
    }

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

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<bool>> adj(n * m, vector<bool>(n * m, false));
    for (int i = 0; i < n; i++) {
        for (int l = 0; l < m; l++) {
            int pos = i * m + l;
            if (i - 1 >= 0) adj[pos][(i - 1) * m + l] = true;
            if (i + 1 < n) adj[pos][(i + 1) * m + l] = true; 
            if (l - 1 >= 0) adj[pos][i * m + (l - 1)] = true;
            if (l + 1 < m) adj[pos][i * m + (l + 1)] = true; 
        }
    }

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

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED

Test 19

Verdict: ACCEPTED

Test 20

Verdict: ACCEPTED

Test 21

Verdict: TIME LIMIT EXCEEDED

Test 22

Verdict: ACCEPTED

Test 23

Verdict: TIME LIMIT EXCEEDED

Test 24

Verdict: ACCEPTED

Test 25

Verdict: ACCEPTED

Test 26

Verdict: ACCEPTED

Test 27

Verdict: RUNTIME ERROR

*** stack smashing detected ***: terminated

Test 28

Verdict: TIME LIMIT EXCEEDED

Test 29

Verdict: TIME LIMIT EXCEEDED

Test 30

Verdict: TIME LIMIT EXCEEDED

Test 31

Verdict: TIME LIMIT EXCEEDED

Test 32

Verdict: TIME LIMIT EXCEEDED

Test 33

Verdict: RUNTIME ERROR

*** stack smashing detected ***: terminated

Test 34

Verdict: TIME LIMIT EXCEEDED

Test 35

Verdict: TIME LIMIT EXCEEDED

Test 36

Verdict: ACCEPTED

Test 37

Verdict: TIME LIMIT EXCEEDED

Test 38

Verdict: TIME LIMIT EXCEEDED

Test 39

Verdict: TIME LIMIT EXCEEDED

Test 40

Verdict: TIME LIMIT EXCEEDED

Test 41

Verdict: TIME LIMIT EXCEEDED

Test 42

Verdict: TIME LIMIT EXCEEDED

Test 43

Verdict: TIME LIMIT EXCEEDED

Test 44

Verdict: TIME LIMIT EXCEEDED

Test 45

Verdict: TIME LIMIT EXCEEDED

Test 46

Verdict: TIME LIMIT EXCEEDED

Test 47

Verdict: RUNTIME ERROR

Test 48

Verdict: RUNTIME ERROR

Test 49

Verdict: RUNTIME ERROR

Test 50

Verdict: TIME LIMIT EXCEEDED

Test 51

Verdict: RUNTIME ERROR

Test 52

Verdict: TIME LIMIT EXCEEDED

Test 53

Verdict: RUNTIME ERROR

Test 54

Verdict: TIME LIMIT EXCEEDED

Test 55

Verdict: TIME LIMIT EXCEEDED

Test 56

Verdict: RUNTIME ERROR

*** stack smashing detected ***: terminated