Untitled

#include<iostream>
using namespace std;
int T,R,C,n,a[101][101],visited[101][101];
const int MAX=50000;
int dirty[2][101];
int dr[4]={0,-1,0,1};
int dc[4]={-1,0,1,0};
int idx;
int ke[11][11];
int sum;
int answer;
int visited2[101];
int flag=true;
struct Queue
{
	int queue[MAX];
	int front;
	int rear;
	Queue(){
		reset();
	}
	void reset(){
		front=-1;
		rear=-1;
	}
	void push(int value){
		queue[++rear]=value;
	}
	int pop(){
		return queue[++front];
	}
	bool isEmpty(){
		return front==rear;
	}
};
void resetVisited(){
	for (int i=0 ;i<R;i++){
		for (int j=0 ;j<C;j++){
			visited[i][j]=0;
		}
	}
}
void resetVisited2(){
	for (int i=0 ;i<R;i++){
			visited2[i]=0;
	}
}
int checkVisited2(){
	for (int i=0 ;i<idx;i++){
		if(visited2[i]==0) return 0;
	}
	return 1;

}
void tinh(int x,int cnt){
	//if(x>idx) return ;
	if(cnt==idx&&checkVisited2()){
		if(sum<answer) answer=sum;
	}
	if(sum>answer) return;

	for (int i=0 ;i<idx;i++){
		if(!visited2[i]){
			sum+=ke[x][i];
			visited2[i]=1;
			tinh(i,cnt+1);
			sum-=ke[x][i];
			visited2[i]=0;
		}
	}
}



void bfs(int x,int y,int index){
	Queue q;
	q.push(x);
	q.push(y);
	visited[x][y]=1;
	while(!q.isEmpty()){
		int r=q.pop();
		int c=q.pop();
		for (int i=0 ;i<4;i++){
			int _r=r+dr[i];
			int _c=c+dc[i];
			if(_r>=0&&_c>=0&&_r<R&&_c<C&&visited[_r][_c]==0&&a[_r][_c]!=2){
				q.push(_r);
				q.push(_c);
				visited[_r][_c]=visited[r][c]+1;
			}
		}
	}
	for (int i=0 ;i<idx;i++){
		ke[index][i]=visited[dirty[0][i]][dirty[1][i]]-1;
		if(ke[index][i]==-1) flag=false;
	}
}

int main(){
	freopen("input.txt","r",stdin);
	cin>>T;
	for (int t=1;t<=T;t++){
		cin>>R>>C;
		idx=1;
		answer=99999;
		sum=0;
		flag=true;
		for (int i=0 ;i<R;i++){
			for (int j=0 ;j<C;j++){
				cin>>a[i][j];
				if(a[i][j]==3){
					dirty[0][0]=i;
					dirty[1][0]=j;
				}
				if(a[i][j]==1){
					dirty[0][idx]=i;
					dirty[1][idx]=j;
					idx++;
				}
			}
		}

		for (int i=0 ;i<idx;i++){
			resetVisited();
			bfs(dirty[0][i],dirty[1][i],i);
		}
		resetVisited2();
		tinh(0,0);
		if(!flag){
			cout<<"Case #"<<t<<endl;
			cout<<-1<<endl;
		}
		else{
			cout<<"Case #"<<t<<endl;
			cout<<answer<<endl;
		}
	}

	return 0;
}