## 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; }