Chess board tour

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

bool isWithinBounds(int nx, int ny, int n, int m) {
    return nx >= 0 && ny >= 0 && nx < n && ny < m;
}

bool hamCycleUtil(int x, int y, int n, int m, int pos, int path[], int visited) {

    int dx[] = {1, 0, -1, 0};
    int dy[] = {0, 1, 0, -1};

    if (pos == n * m) {
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k], ny = y + dy[k];
            if (nx == 0 && ny == 0) return true;
        }
        return false;
    }

    for (int k = 0; k < 4; k++) {
        int nx = x + dx[k];
        int ny = y + dy[k];
        int nextPos = nx * m + ny;

        if (isWithinBounds(nx, ny, n, m) && !(visited & (1 << nextPos))) {
            visited |= (1 << nextPos);
            path[pos] = nextPos;

            if (hamCycleUtil(nx, ny, n, m, pos + 1, path, visited)) return true;

            visited &= ~(1 << nextPos);
        }
    }
    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(int n, int m) {
    int V = n * m;
    int path[V];
    int visited = 1;

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

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

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

int main() {
    int n, m;
    cin >> n >> m;

    hamCycle(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: WRONG ANSWER

Test 18

Verdict: WRONG ANSWER

Test 19

Verdict: ACCEPTED

Test 20

Verdict: ACCEPTED

Test 21

Verdict: WRONG ANSWER

Test 22

Verdict: ACCEPTED

Test 23

Verdict: WRONG ANSWER

Test 24

Verdict: ACCEPTED

Test 25

Verdict: ACCEPTED

Test 26

Verdict: ACCEPTED

Test 27

Verdict: TIME LIMIT EXCEEDED

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: ACCEPTED

Test 33

Verdict: WRONG ANSWER

Test 34

Verdict: TIME LIMIT EXCEEDED

Test 35

Verdict: WRONG ANSWER

Test 36

Verdict: WRONG ANSWER

Test 37

Verdict: TIME LIMIT EXCEEDED

Test 38

Verdict: TIME LIMIT EXCEEDED

Test 39

Verdict: TIME LIMIT EXCEEDED

Test 40

Verdict: WRONG ANSWER

Test 41

Verdict: WRONG ANSWER

Test 42

Verdict: TIME LIMIT EXCEEDED

Test 43

Verdict: WRONG ANSWER

Test 44

Verdict: ACCEPTED

Test 45

Verdict: WRONG ANSWER

Test 46

Verdict: WRONG ANSWER

Test 47

Verdict: TIME LIMIT EXCEEDED

Test 48

Verdict: TIME LIMIT EXCEEDED

Test 49

Verdict: TIME LIMIT EXCEEDED

Test 50

Verdict: TIME LIMIT EXCEEDED

Test 51

Verdict: TIME LIMIT EXCEEDED

Test 52

Verdict: TIME LIMIT EXCEEDED

Test 53

Verdict: TIME LIMIT EXCEEDED

Test 54

Verdict: TIME LIMIT EXCEEDED

Test 55

Verdict: TIME LIMIT EXCEEDED

Test 56

Verdict: TIME LIMIT EXCEEDED