Getting WA for H1 (A Puzzle Game) with Recursive backtracking

general
, ,
1

I am not sure why I am getting the wrong answer for this question: A Puzzle Game (Problem code: H1) even though the sample test cases work fine. Could someone please help me understand my mistake? I am using recursive backtracking for solving with the following code:

#include <bits/stdc++.h>
#include <numeric>
using namespace std;

#define ll long long
#define fo(i,a,n) for(i = (a); i < (n); i++)
#define foi(i,a,n) for(i = (a); i <= (n); i++)
#define cases int t;cin>>t;while(t--)
#define N 3

int primes[20]={0,0,1,1,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1};
int row(int index){
 return index/3;
}
int col(int index){
 return index%3;
}
int manhattanOf(int num, int r, int c){
 --num;
 return abs(r-row(num))+abs(c-col(num));
}
bool canSwap(int arr[N][N], int i1, int j1, int i2, int j2, int manhattan[N*N+1], int invcount) {
 int m1 = manhattanOf(arr[i1][j1],i2,j2), m2 = manhattanOf(arr[i2][j2],i1,j1);
 if ((m1+m2) > (manhattan[arr[i1][j1]] + manhattan[arr[i2][j2]])) return false;
 return true;
}
void swap(int arr[N][N], int i1, int j1, int i2, int j2, int manhattan[N*N+1], int& invcount){
 int m1 = manhattanOf(arr[i1][j1],i2,j2), m2 = manhattanOf(arr[i2][j2],i1,j1);
 invcount += m1-manhattan[arr[i1][j1]];
 invcount += m2-manhattan[arr[i2][j2]];
 manhattan[arr[i1][j1]] = m1;
 manhattan[arr[i2][j2]] = m2;
 int temp = arr[i1][j1];
 arr[i1][j1] = arr[i2][j2];
 arr[i2][j2] = temp;
}


int getCount(int arr[N][N], int manhattan[N*N+1], int invcount, bool vis[N*N+1][N*N+1]) {
 if (invcount<=0) return 0;
 int count=INT_MAX-1;
 for (int i=0;i<N;++i){
 	for (int j=0;j<N;++j){
 		if (i>0) {
 			int e1 = arr[i][j], e2 = arr[i-1][j];
 			if (primes[e1+e2] && !vis[e1][e2] && !vis[e2][e1]) {			
 				if (canSwap(arr, i, j, i-1, j, manhattan, invcount)) {
 					swap(arr, i, j, i-1, j, manhattan, invcount);
 					vis[e1][e2] = vis[e2][e1] = true;
 					count=min(count, 1+getCount(arr, manhattan, invcount, vis));
 					swap(arr, i, j, i-1, j, manhattan, invcount);
 					vis[e1][e2] = vis[e2][e1] = false;
 				}
 			}
 		}
 		if (j>0) {
 			int e1 = arr[i][j], e2 = arr[i][j-1];
 			if (primes[e1+e2] && !vis[e1][e2] && !vis[e2][e1]) {			
 				if (canSwap(arr, i, j, i, j-1, manhattan, invcount)) {
 					swap(arr, i, j, i, j-1, manhattan, invcount);
 					vis[e1][e2] = vis[e2][e1] = true;
 					count = min(count,1 + getCount(arr, manhattan, invcount, vis));
 					swap(arr, i, j, i, j-1, manhattan, invcount);
 					vis[e1][e2] = vis[e2][e1] = false;
 				}
 			}
 		}
 	}
 }
 return count;
}

int solve(int arr[N][N]) {
 int i,j,manhattan[N*N+1],invcount=0;
 bool present[N*N+1]={false};
 bool vis[N*N+1][N*N+1];
 fo(i,0,N) {
 	fo(j,0,N) {
 		int e = arr[i][j];
 		if (e<=0||e>9) return -1;
 		if (present[e]) return -1;
 		manhattan[arr[i][j]] = manhattanOf(arr[i][j],i,j);
 		invcount += manhattan[arr[i][j]];
 	}
 }
 foi(i,0,N*N) foi(j,0,N*N) vis[i][j]=false;

 int count=getCount(arr,manhattan,invcount,vis);
 return ((count<INT_MAX-1)?count:-1);
}

int main(int argc, char const *argv[])
{
 cases{
 	int arr[N][N]={0},i,j;
 	fo(i,0,N) fo(j,0,N) cin>>arr[i][j];
 	cout<<solve(arr)<<endl;
 }
 return 0;
}