Jewels_&_maze_Samsung

/*
test cases
2
5
0 0 0 2 0
2 1 0 1 2
0 0 2 2 0
0 1 0 1 2
2 0 0 0 0
6
0 1 2 1 0 0
0 1 0 0 0 1
0 1 2 1 2 1
0 2 0 1 0 2
0 1 0 1 0 1
2 0 2 1 0 0

output:-
3 0 3 3 3
3 1 3 1 3
3 0 3 2 3
3 1 3 1 3
3 3 3 0 3
6
3 1 2 1 0 0
3 1 3 3 3 1
3 1 3 1 3 1
3 2 3 1 3 2
3 1 3 1 3 1
3 3 3 1 3 3
4
*/

#include <iostream>
using namespace std;

int n;
int mat[100][100];
int sec[100][100];
bool visited[199][100];
int ans=-1;

bool canCheck(int x, int y){
    if(x>=0 && x<n && y>=0 && y<n && mat[x][y]!=1 && visited[x][y]==false)
        return true;
    return false;
}

void print(){
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cout<<mat[i][j]<<" ";
        }
        cout<<endl;
    }
    cout<<endl;
}

void solve(int x,int y,int jewels, int my_ans = 999999){
    if(x==n-1 && y==n-1){
        ans=max(ans,jewels);
        if (ans == my_ans) print();
        return;
    }

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

    for(int i=0; i<4; i++){
        int m = x + dx[i];
        int n = y+ dy[i];

        if(canCheck(m,n)){
            visited[m][n]=true;

            if(mat[m][n]==2){
                mat[m][n]=3;
                solve(m,n,jewels +1, my_ans);
            }
            else {
                mat[m][n]=3;
                solve(m,n,jewels, my_ans);
            }
            visited[m][n]=false;
            mat[m][n]=sec[m][n];
        }
    }
}

int main() {
    int t;
    cin>>t;
    while(t--){
        cin>>n;

        ans=-1;
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
                cin>>mat[i][j];

        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
                sec[i][j] = mat[i][j];

        visited[10][10]={false};

        visited[0][0]=true;
        mat[0][0]=3;

        solve(0,0,0); // statarting cordinates and no of jewels
        cout<<ans<<endl;
        int my_ans = ans;
        ans = -1;
        solve(0,0,0,my_ans);

    }
}