Untitled

#include <iostream>

using namespace std;

int T, N, M;
int arr[105][105];
int posX[11];
int posY[11];
int visited[105][105];

int map[11][11];
int k;
int ans, minA;
int x, y;

class Queue{
	int front, rear;
	int q[1000000];
public:
	Queue();
	void enQueue(int value);
	int deQueue();
	void reset();
	bool is_Empty();
};

Queue::Queue(){
	front = rear = -1;
}
void Queue::enQueue(int value){
	q[++rear] = value;
}
int Queue::deQueue(){
	return q[++front];
}
void Queue::reset(){
	front = rear = -1;
}
bool Queue::is_Empty(){
	if(front == rear)
		return true;
	return false;
}

int X[4] = {-1, 1, 0, 0};
int Y[4] = {0, 0, 1, -1};

int check[11];
Queue rQueue, cQueue;
int init[105][105];
int cnt;

void backtrack(int n, int tmp){
	if(ans >= minA){
		return;
	}
	if(tmp == k){
		if(ans < minA) 
			minA = ans;
		return;
	}
	for(int i = 1; i < k; i++){
		if(map[n][i] != 0 && check[i] == 0 ){
			ans += map[n][i];
			check[i] = 1;
			backtrack(i, tmp + 1);
			ans -= map[n][i];
			check[i] = 0;
		}
	}
}

void BFS(int x, int y){
	int a = posX[x];
	int b = posY[x];

	int c = posX[y];
	int d = posY[y];

	for(int i = 0; i < N; i++){
		for(int j = 0; j < M; j++){
			visited[i][j] = 0;
			init[i][j] = arr[i][j];
		}
	}

	rQueue.reset();
	cQueue.reset();

	init[a][b] = 0;
	visited[a][b] = 1;

	rQueue.enQueue(a);
	cQueue.enQueue(b);

	int flag;

	while(rQueue.is_Empty() == false){
		flag = 0;
		int x1 = rQueue.deQueue();
		int y1 = cQueue.deQueue();

		for(int i = 0; i < 4; i++){
			int row = x1 + X[i];
			int col = y1 + Y[i];
			if(row >= 0 && row < N && col >= 0 && col < M && visited[row][col] == 0 && init[row][col] != 2){
				if(row == c && col == d){
					init[row][col] = init[x1][y1] + 1;
					map[x][y] = init[row][col];
					map[y][x] = init[row][col];
					flag = 1;
					break;
				}else{
					init[row][col] = init[x1][y1] + 1;
					visited[row][col] = 1;
					rQueue.enQueue(row);
					cQueue.enQueue(col);
				}
			}
			if(flag == 1){
				break;
			}
		}
		if(flag == 1){
			break;
		}
	}
	if(init[c][d] == -1 || init[c][d] == -3){
		map[x][y] = 0;
		map[y][x] = 0;
	}
}


int main(){
	freopen("input.txt", "rt", stdin);
	cin >> T;
	for(int tc = 1; tc <= T; tc++){
		cin >> N >> M;
		for(int i = 0; i < N; i++){
			for(int j = 0; j < M; j++){
				cin >> arr[i][j];
				if(arr[i][j] == 3){
					x = i;
					y = j;
					arr[i][j] = -3;
				}
			}
		}
		posX[0] = x;
		posY[0] = y;
		k = 1;
		for(int i = 0; i < N; i++){
			for(int j = 0; j < M; j++){
				if(arr[i][j] == 1){
					arr[i][j] = -1;
					posX[k] = i;
					posY[k] = j;
					k++;
				}
			}
		}
		for(int i = 0; i < k - 1; i++){
			for(int j = i + 1; j < k; j++){
				BFS(i, j);
			}
		}
		for(int i = 0; i < k; i++){
			check[i] = 0;
		}
		ans = 0;
		minA = 1000000;
		backtrack(0, 1);
		cout << "Case #" << tc << endl;
		if(minA == 1000000){
			cout << -1 << endl;
		}else{
			cout << minA << endl;
		}
	}
	while(1);
	return 0;
}