Untitled

#include<iostream>

using namespace std;

int t,m,n,dem,dis,ans,flag;
int mang[100][100];
int visit[100][100];
int map[11][11];
bool visited[11];

int mover[4]={-1,0,1,0};
int movec[4]={0,1,0,-1};

void resetvisit(){
	for(int i=0;i<m;i++){
		for(int j=0;j<n;j++) visit[i][j]=-1;
	}
}

struct point{
	int x,y;
};

point dirty[11];
int index;

class queue{
	int front,rear;
	point arr[100000];
public:
	queue(){
		rear=-1; front=-1;
	}
	bool isempty(){
		return(rear==front);
	}
	point peek(){
		return arr[front+1];
	}
	void push(point a){
		rear++;
		arr[rear]=a;
	}
	void pop(){
		front++;
	}
	void reset(){
		rear=-1; front=-1;
	}
};

queue q;

void bfs(point a){
	q.reset(); resetvisit();
	q.push(a);
	visit[a.x][a.y]=0;
	while(!q.isempty()){
		point v=q.peek();
		q.pop();
		for(int h=0;h<4;h++){
			point u;
			u=v;
			u.x+=mover[h]; u.y+=movec[h];
			if(u.x>=0 && u.x<m && u.y>=0 && u.y<n && visit[u.x][u.y]==-1 && mang[u.x][u.y]!=2){
				q.push(u); visit[u.x][u.y]=visit[v.x][v.y]+1;
			}
		}
	}
}

void mahoa(){
	for(int i=0;i<=dem;i++){
		bfs(dirty[i]);
		for(int j=i;j<=dem;j++){
			if(i==j) map[i][j]=0; 
			else {
				map[i][j]=visit[dirty[j].x][dirty[j].y];
				map[j][i]=map[i][j];
			}
		}
	}
}

void bt(int x, int cnt){
	if(cnt==dem){
		if(dis<ans) ans=dis;
		return;
	}
	else if(dis<ans){
		for(int i=1;i<=dem;i++){
			if(!visited[i]){
				visited[i]=true;
				dis+=map[x][i];
				bt(i,cnt+1);
				visited[i]=false;
				dis-=map[x][i];
			}
		}
	}
}


int main(){
	//freopen("input.txt","r",stdin);
	cin >> t;
	for(int tc=1;tc<=t;tc++){
		cin >> m >> n;
		dem=0; index=1;
		for(int i=0;i<m;i++){
			for(int j=0;j<n;j++) {
				cin >> mang[i][j];
				if(mang[i][j]==1) {
					dem++;
					dirty[index].x=i; dirty[index].y=j; index++;
				}
				if(mang[i][j]==3){
					dirty[0].x=i; dirty[0].y=j;
				}
			}
		}
		flag=0;
		mahoa();
		for(int j=1;j<=dem;j++){
			//cout<<map[0][j]<<" ";
			if(map[0][j]==-1){
				flag=1;
				break;
			}
		}
		//cout<<endl;
		if(flag==1) {
			cout << "Case #" << tc << endl;
			cout << "-1" << endl;
			
		}
		else{
			for(int i=1;i<=dem;i++) visited[i]=false;
			ans=100000; dis=0;
			bt(0,0);
			cout << "Case #" << tc << endl;
			cout << ans << endl;
		}
	}

	return 0;
}