Untitled

#include<iostream>

using namespace std;

#define INF 10000007

typedef struct
{
	int x,y;
}o_xy;

int dx[8] = {-2,-1,1,2,2,1,-1,-2};
int dy[8] = {1,2,2,1,-1,-2,-2,-1};

int N, M;
int map[105][105]; // mang input

o_xy mapPosition[10000];
int index; // index cua quan dich trong map Position

int mapDistance[105][105]; // luu khoang cach giua cac doi tuong

o_xy queue[1000000];
int visited[105][105];
int r = -1, f = -1;

int visitedBT[10000];

void push(o_xy obj)
{
	r++;
	queue[r] = obj;
}

void pop(o_xy &obj)
{
	f++;
	obj = queue[f];
}

bool isSafe(o_xy obj)
{
	if(obj.x >= 0 && obj.x < N && obj.y >= 0 && obj.y < M)
		return true;
	return false;
}

void BFS(o_xy pre)
{
	push(pre);
	visited[pre.x][pre.y] = 0;

	while(r != f)
	{
		pop(pre);

		for(int i = 0; i < 8; i++)
		{
			o_xy next;
			next.x = pre.x + dx[i];
			next.y = pre.y + dy[i];

			if(isSafe(next) && visited[next.x][next.y] == -1)
			{
				visited[next.x][next.y] = visited[pre.x][pre.y] + 1;
				push(next);
			}
		}
	}
}

int minAns = INF;

void backTrack(int k, int sum, int u)
{
	if(sum > minAns)	return;

	if(k == index)
	{
		minAns = sum < minAns ? sum : minAns;
		return;
	}

	for(int v = 1; v <= index; v++)
	{
		if(visitedBT[v] == 0)
		{
			visitedBT[v] = 1;
			backTrack(k + 1, sum + mapDistance[u][v], v);
			visitedBT[v] = 0;
		}
	}
}


void resetVisitedBT()
{
	for(int i = 0; i < 10000; i++)
		visitedBT[i] = 0;

}

void resetQueue()
{
	r = f = -1;
	for(int i = 0; i < N; i++)
		for(int j = 0; j < M; j++)
			visited[i][j] = -1;

}

int main()
{
	//freopen("Text.txt","r",stdin);
	int T;
	cin>>T;

	for(int tc = 1; tc <= T; tc++)
	{
		index = 0;
		minAns = INF;
		resetQueue();
		resetVisitedBT();
		cin>>N>>M;

		for(int i = 0; i < N; i++)
		{
			for(int j =0; j < M; j++)
			{
				cin >> map[i][j];
				if(map[i][j] == 3)
				{
					mapPosition[0].x = i;
					mapPosition[0].y = j;
				}
				if(map[i][j] == 1)
				{
					index++;
					mapPosition[index].x = i;
					mapPosition[index].y = j;
				}
			}
		}
	// BFS khoang cach cac diem
		for(int i = 0; i <= index; i++)
		{
			resetQueue();
			BFS(mapPosition[i]);
			for(int j = 0; j <= index; j++)
			{
				mapDistance[i][j] = mapDistance[j][i] = visited[mapPosition[j].x][mapPosition[j].y];
			}
			//resetQueue();
		}
	// BackTrack
		backTrack(0,0,0);

		cout<<"Case #"<<tc<<endl;
        cout<<minAns<<endl;

	}
	return 0;
}