Untitled

#include <iostream>
#define N 101
#define oo 2000000009
using namespace std;
int n,m;
int a[N][N];
int d[N][N];
int ans;
//0 : a clean tile
//1 : a dirty tile
//2 : a piece of furniture (obstacle)
//3 : the robot (initial position)
int cnt;
int kc[11][11];
int x,y;

int sx[N*N];
int sy[N*N];
int hx[]={0,-1,0,1};
int hy[]={-1,0,1,0};
int dd[N][N];
int tt[N];
void doc()
{
	cnt=0;
	ans=oo;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			d[i][j]=0;
			cin>>a[i][j];
			if(a[i][j]==1)
				{
					cnt++;
					d[i][j]=cnt;
			}
			if(a[i][j]==3)x=i,y=j;
		}

		for(int i=0;i<=cnt;i++)
			for(int j=0;j<=cnt;j++)kc[i][j]=0;
}

void bfs(int u, int v)
{
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)dd[i][j]=0;

	int dau=1,cuoi=0;
	sx[++cuoi]=u;
	sy[cuoi]=v;
	dd[u][v]=1;
	while(dau<=cuoi)
	{
		int xx=sx[dau];
		int yy=sy[dau];
		dau++;
		for(int i=0;i<4;i++)
		{
			int uu=xx+hx[i];
			int vv=yy+hy[i];

			if(uu>0&&uu<=n&&vv>0&&vv<=m&&dd[uu][vv]==0&&a[uu][vv]!=2)
			{
				dd[uu][vv]=dd[xx][yy]+1;
				sx[++cuoi]=uu;
				sy[cuoi]=vv;
			}
		}
	}
}
int vs[12];
void backtrack(int u,int sum)
{
	if(u==cnt+1)
	{
		if(ans>sum)ans=sum;
		return;
	}
	for(int i=1;i<=cnt;i++)
        if (vs[i]==0 && sum+kc[tt[u-1]][i]<ans && kc[tt[u-1]][i])
	{
		vs[i]=1;
		tt[u]=i;
		backtrack(u+1,sum+kc[tt[u-1]][i]);
		vs[i]=0;
	}

}
int main()
{
	//freopen("input.txt","r",stdin);
	int TC;
	
	cin>>TC;
	
	for(int tc=1;tc<=TC;tc++)
	{
		doc();
		bfs(x,y);
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)if(a[i][j]==1&&dd[i][j])kc[0][d[i][j]]=dd[i][j]-1;

		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)if(a[i][j]==1)
			{
				bfs(i,j);
				for(int ii=1;ii<=n;ii++)
					for(int jj=1;jj<=m;jj++)if(a[ii][jj]==1&&dd[ii][jj])kc[d[i][j]][d[ii][jj]]=dd[ii][jj]-1;
			}
			
		tt[0]=0;
		backtrack(1,0);
		if(ans==oo)ans=-1;
		cout<<"Case #"<<tc<<"\n";
		cout<<ans<<"\n";
	}
	return 0;
}