Chess board tour

input/code.cpp: In function 'void dfs(std::vector<std::vector<bool> >, std::vector<char>&, bool&, std::pair<int, int>, std::vector<char>&)':
input/code.cpp:19:50: warning: comparison of integer expressions of different signedness: 'std::vector<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   19 |         if (pos == make_pair(0,0) and sol.size() == rows * cols) {
      |                                       ~~~~~~~~~~~^~~~~~~~~~~~~~
input/code.cpp:26:184: warning: comparison of integer expressions of different signedness: 'std::vector<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   26 |             if (!solution and correct_position(rows, cols, {pos.first, pos.second+1}) and (!visited[pos.first][pos.second+1] or (pos.first == 0 and pos.second + 1 == 0 and sol.size() == rows*cols-1))) {
      |...

#include <bits/stdc++.h>

using namespace std;

bool correct_position(int rows, int cols, pair<int, int> pos) {
    return pos.first >= 0 and pos.first < rows and pos.second >= 0 and pos.second < cols;
}

void dfs(vector<vector<bool>> visited, vector<char> &sol, bool &solution, pair<int, int> pos, vector<char> &final_sol) {
    /*cout << "CURRENTLY VISITING " << pos.first << " " << pos.second << endl;
    cout << "The sol until now is: ";
    for (int i = 0; i < sol.size(); ++i)
        cout << sol[i] << " ";
    cout << endl;*/
    
    int rows = visited.size();
    int cols = visited[0].size();
    if (correct_position(rows, cols, pos)) {
        if (pos == make_pair(0,0) and sol.size() == rows * cols) {
            // Solution found
            //cout << "SOLUTION FOUND" << endl;
            solution = true;
            final_sol = sol;
        }
        else {
            if (!solution and correct_position(rows, cols, {pos.first, pos.second+1}) and (!visited[pos.first][pos.second+1] or (pos.first == 0 and pos.second + 1 == 0 and sol.size() == rows*cols-1))) {
                sol.push_back('R');
                visited[pos.first][pos.second + 1] = true;
                dfs(visited, sol, solution, {pos.first, pos.second + 1}, final_sol);
                sol.pop_back();
                visited[pos.first][pos.second + 1] = false;
            }
            if (!solution and correct_position(rows, cols, {pos.first, pos.second-1}) and (!visited[pos.first][pos.second-1] or (pos.first == 0 and pos.second - 1 == 0 and sol.size() == rows*cols-1))) {
                sol.push_back('L');
                visited[pos.first][pos.second - 1] = true;
                dfs(visited, sol, solution, {pos.first, pos.second - 1}, final_sol);
                sol.pop_back();
                visited[pos.first][pos.second - 1] = false;
            }
            if (!solution and correct_position(rows, cols, {pos.first+1, pos.second}) and (!visited[pos.first+1][pos.second] or (pos.first + 1 == 0 and pos.second == 0 and sol.size() == rows*cols-1))) {
                sol.push_back('D');
                visited[pos.first+1][pos.second] = true;
                dfs(visited, sol, solution, {pos.first+1, pos.second}, final_sol);
                sol.pop_back();
                visited[pos.first+1][pos.second] = false;
            }
            if (!solution and correct_position(rows, cols, {pos.first-1, pos.second}) and (!visited[pos.first-1][pos.second] or (pos.first - 1 == 0 and pos.second == 0 and sol.size() == rows*cols-1))) {
                sol.push_back('U');
                visited[pos.first-1][pos.second] = true;
                dfs(visited, sol, solution, {pos.first-1, pos.second}, final_sol);
                sol.pop_back();
                visited[pos.first-1][pos.second] = false;
            }
        }

        
    }
}

void print_sol(vector<char> &sol) {
    for (int i = 0; i < sol.size(); ++i)
        cout << sol[i];
    cout << endl;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, m;
    cin >> n >> m;

    vector<vector<bool>> visited(n, vector<bool>(m, false));
    visited[0][0] = true;
    vector<char> sol(0);
    vector<char> final_sol;
    bool solution = false;

    dfs(visited, sol, solution, {0,0}, final_sol);

    if (solution)
        print_sol(final_sol);
    else
        cout << -1 << endl;
}

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: 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: TIME LIMIT EXCEEDED

Test 33

Verdict: TIME LIMIT EXCEEDED

Test 34

Verdict: TIME LIMIT EXCEEDED

Test 35

Verdict: TIME LIMIT EXCEEDED

Test 36

Verdict: TIME LIMIT EXCEEDED

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: TIME LIMIT EXCEEDED

Test 50

Verdict: RUNTIME ERROR

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: RUNTIME ERROR

Test 56

Verdict: TIME LIMIT EXCEEDED