COMCB-Complete Chess Boards

Complete Chess Boards

Given below c++11 code is for COMCB spoj or Complete Chess Boards spoj.

Hint :- dfs with backtracking ,

for each node apply DFS and check if traversal of chess board is possible or not . Inside send child node in lexicographical order so that final path will be lexicographically shortest.

/*
===================================================
Name :- Nishant Raj
Email :- raj.nishant360@gmail.com
College :- Indian School of Mines
Branch :- Computer Science and Engineering
Time :- 17 August 2015 (Monday) 04:58
===================================================*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair < int , int >
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define mod 1000000009
int x[8] = {-1,1,-2,2,-2,2,-1,1};
int y[8] = {-2,-2,-1,-1,1,1,2,2};
int n , m;
bool valid(int row , int col){
    if(row>=0 && row< n && col >=0 && col < m)
        return true;
    return false;
}
bool dfs(vector<string> path ,int row ,int col , int count, int check[][30]){
    string temp = "";
    char c = (char)(col + 65);
    temp.pb(c);
    temp.append(to_string(row+1));
    path.pb(temp);
    if(count == m*n){
        for(int i = 0 ; i < path.size() ; i++)
            cout<<path[i];
        cout<<endl;
        return true;
    }
    int p , q;
    for(int i = 0 ; i < 8 ; i++){
        p = row + x[i] , q = col + y[i];
        if(valid(p , q) && !check[p][q]){
            check[p][q] = 1;
            if(dfs( path , p , q , count+1 , check)) return true;
            check[p][q] = 0;
        }
    }
    return false;
}
bool path(){
    for(int i = 0 ; i < n; i ++){
        for(int j = 0 ; j < m ; j++){
            int check[30][30];
            memset(check , 0 , sizeof check);
            check[i][j] = 1;
            vector<string> path;
            if(dfs(path , i , j ,1 , check )) return true;
        }
    }
    return false;
}
int main(){ 
     
    int t;
    cin>>t;
    while(t--){
        cin>>n>>m;
        if(!path()) cout<<-1<<endl;
    }
    
    return 0;
}