Untitled

#include <iostream>
#define MIN 999999999
using namespace std;

int arr[101][101];
int n, m;
int dR[8] = {-1, -2, -2, -1, 1, 2, 2, 1};
int dC[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int len[101][101];
int visited[101][101];
int visited1[101];
int dem;
int kc[101][101][101];
int Min;
int cost;


typedef struct Point
{
	int x, y;
};

Point D[101];

typedef struct Queue{
	int front, rear;
	Point data[1000001];
};

void init(Queue &Q){
	Q.front = Q.rear = -1;
}

void push(Queue &Q, Point value){
	Q.rear++;
	Q.data[Q.rear] = value;
}

Point top(Queue &Q){
	Point temp;
	Q.front++;
	temp = Q.data[Q.front];
	Q.front--;
	return temp;
}

void pop(Queue &Q){
	Q.front++;
}

bool empty(Queue &Q){
	if(Q.front == Q.rear)
		return true;
	return false;
}

Queue Q;

void BFS(Point P){
	init(Q);
	push(Q, P);
	visited[P.x][P.y] = 1;
	len[P.x][P.y] = 0;

	while(!empty(Q)){
		Point P1;
		P1 = top(Q);
		pop(Q);

		for(int k=0; k<8; k++){
			int x = P1.x + dR[k];
			int y = P1.y + dC[k];

			if(x>=0 && x<n && y>=0 && y<m && visited[x][y] == 0){
				visited[x][y] = 1;
				len[x][y] = len[P1.x][P1.y] + 1;

				Point P2;
				P2.x = x;
				P2.y = y;
				push(Q, P2);
			}
		}
	}
}

void BackTrack(int i, int k){

	if(k == dem){
		Min = min(Min, cost);
		return;
	}

	if(cost >= Min){
		return;
	}

	for(int j=1; j<dem; j++){

		if(visited1[j] == 0 && i!=j){
			visited1[j] = 1;
			cost += kc[i][D[j].x][D[j].y];

			BackTrack(j, k + 1);

			visited1[j] = 0;
			cost -= kc[i][D[j].x][D[j].y];
		}

	}
}

int main(){
	freopen("vao.txt", "r", stdin);
	int t;
	cin >> t;
	for(int tc=1; tc<=t; tc++){

		cin >> n >> m;

		int xm = -1, ym = -1;
		dem = 1;
		for(int i=0; i<n; i++){
			for(int j=0; j<m; j++){
				cin >> arr[i][j];
				if(arr[i][j] == 3 && xm == -1){
					D[0].x = i;
					D[0].y = j;
				}
				if(arr[i][j] == 1){
					D[dem].x = i;
					D[dem].y = j;
					dem++;
				}
			}
		}

		for(int k=0; k<dem; k++){

			for(int i=0; i<n; i++){
				for(int j=0; j<m; j++){
					visited[i][j] = 0;
					len[i][j] = 0;
				}
			}

			Point P;
			P.x = D[k].x;
			P.y = D[k].y;

			BFS(P);

			for(int l=0; l<dem; l++){
				kc[k][D[l].x][D[l].y] = len[D[l].x][D[l].y];
			}

		}

		Min = MIN;
		visited1[0] = 1;
		cost = 0;
		BackTrack(0, 1);
		cout << "Case #" << tc << endl;
		cout << Min << endl;
	}
	return 0;
}