Untitled

#include<iostream>
using namespace std;
#define sach 0
#define ban 1
#define chuongngai 2
#define rbbandau 3
const int maxq=10000;

// thu vien str copy
void strcpy(char *src, char *dst){
	int i=0;
	while( src[i]!='\0'){
	     dst[i]=src[i++];
	}
	dst[i]='\0';
}
struct pos{
	int x,y;
};
struct Queue{
	pos q[maxq];
	int top;
	int bot;
	Queue(){
		top=-1;
		bot=-1;
	}
	void reset(){
		top=-1;
		bot=-1;   
	}
	void push(pos value){
		q[++top%maxq]=value;
	}
	pos pop(){
		if(top!=bot)
			return q[++bot%maxq];
	}
	pos peek(){
		if(top!=bot)
			return q[bot++%maxq];
	}
	bool isempty(){
		return bot==top;
	}
};

int m,n,idx,sum,answer;
int map[105][105];
int visit[105][105];
int visit2[15];
int ke[15][15];
int oban[2][15];
bool flag;
int dx[4]={-1,0,1,0};
int dy[4]={0,-1,0,1};
// luu vi tri
void resetvisit(){
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			visit[i][j]=0;
		}
	}
}
void resetvisit2(){
	for(int i=0;i<idx;i++){
		visit2[i]=0;
	}
}
int checkvisit2(){
	for(int i=0;i<idx;i++){
		if(visit2[i]==0)return 0; 
	}
	return 1; // neu ghe tham het cac o ban
}
void tinh(int x,int count){
	if(count==idx && checkvisit2()){
		if(sum<answer)
			answer=sum;
	}
	if(sum>answer)return;
	for(int i=0;i<idx;i++){
		if(!visit2[i]){
			sum+=ke[x][i];
			visit2[i]=1;
			tinh(i,count+1);
			sum-=ke[x][i];
			visit2[i]=0;
		}
	}
}

void bfs(int r,int c,int index){
	Queue q=Queue();
	pos el={r,c};
	q.push(el);
	visit[r][c]=1;
	while(!q.isempty()){
		pos top=q.pop();
		for(int i=0;i<4;i++){
			int x=top.x+dx[i];
			int y=top.y+dy[i];
			if(x>=0 && x<n&& y>=0 &&y<m&& visit[x][y]==0 && map[x][y]!=2)
			{
				visit[x][y]=visit[top.x][top.y]+1;
				pos el={x,y};
				q.push(el);
			}
		}
	}

	// ma tran ke voi hang la index cot lan luot la vi tri o ban
	for(int i=0;i<idx;i++){
		ke[index][i]=visit[oban[0][i]][oban[1][i]]-1;
		if(ke[index][i]==-1) flag=true;// o visit bang 0 tuc laf khong loang vaof dc
	}
	
}
int main(){
	FILE*file;
	freopen_s(&file,"input.txt","r",stdin);
	int t;
	cin>>t;
	for(int testcase =1;testcase<=t;testcase++){
		flag=false;
		//nhap mang  
		cin >>n>>m;
	    for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){
				cin>>map[i][j];
			}
		}
	    // thuc hien
		 idx=1;
		 for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){
				if(map[i][j]==3){
					oban[0][0]=i;// vt robot
				    oban[1][0]=j;
				}
				if(map[i][j]==1){
					oban[0][idx]=i;
					oban[1][idx]=j;// dien xong moi cong nen khong lo vu <idx
					idx++; 
				}
			}
		}
		// duyet ngang
		for (int i=0 ;i<idx;i++){
			resetvisit();
			bfs(oban[0][i],oban[1][i],i); 
		}
		answer=9999999;
		sum=0;
		tinh(0,0);
		// out
		if(flag){
			cout<<"Case #"<<testcase<<endl;
			cout<<-1<<endl;
		}
		else{
			cout<<"Case #"<<testcase<<endl;
			cout<<answer<<endl;
		}

	}
	return 0;
}