Treino W

#include <stdio.h>
#include <stdlib.h>

int tabuleiro[9][9]={{0}};
int movimentoX[4]={-1,0,1,0};
int movimentoY[4]={0,-1,0,1};
int num=10000;


void minMovimentos(int n, int posX, int posY, int numMovimentos,int totalPretas,int numAtual){
    int i, flag,aux;

    if(numMovimentos>=num){
        return;
    }

    if(numAtual==totalPretas){

        if(numMovimentos<num){
            num=numMovimentos;

        }

        return;
    }else{

        for(i=0;i<4;i++){

            if(tabuleiro[posX+movimentoX[i]][posY+movimentoY[i]]!=2 && posX+movimentoX[i]<n && posX+movimentoX[i]>=0 && posY+movimentoY[i]<n && posY+movimentoY[i]>=0){

                if(tabuleiro[posX+movimentoX[i]][posY+movimentoY[i]]==1){
                    numAtual++;
                    flag=1;
                }

                aux=tabuleiro[posX+movimentoX[i]][posY+movimentoY[i]];

                tabuleiro[posX+movimentoX[i]][posY+movimentoY[i]]=2;

                minMovimentos(n,posX+movimentoX[i],posY+movimentoY[i],numMovimentos+1,totalPretas,numAtual);

                tabuleiro[posX+movimentoX[i]][posY+movimentoY[i]]=aux;

                if(flag==1){
                    numAtual--;
                    flag=0;
                }
            }

        }

    }

}

int main()
{
    int i,j,k,n,casos_teste, inicioX=0, inicioY=0, totalPretas=0;
    scanf("%d",&casos_teste);
    for(i=0;i<casos_teste;i++){
        scanf("%d",&n);
        for(j=0;j<n;j++){
            for(k=0;k<n;k++){
                scanf("%d",&tabuleiro[j][k]);
                if(tabuleiro[j][k]==2){
                    inicioX=j;
                    inicioY=k;
                }else if(tabuleiro[j][k]==1){
                    totalPretas++;
                }
            }
        }

        if(totalPretas==0){
            printf("0\n");
        }else if(totalPretas==((n*n)-1)){
            printf("%d\n",((n*n)-1));
        }
        else{

            minMovimentos(n,inicioX,inicioY,0,totalPretas,0);
            printf("%d\n",num);

        }
        num=10000;
        totalPretas=0;

    }
    return 0;
}