Untitled

#include<iostream>
using namespace std;

int T, hang, cot, vtdx, vtdy, vtcx, vtcy;
int a;
int visit[1005][1005], arr[1005][1005];
int front = 0, rear = 0;
int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[] = {1, 2, 2, 1, -1, -2, -2, -1};
int sl, dich[100][100], kc[100][100], mtk[100][100];;
int rs;
int vs[100];

struct toado
{	int x;
	int y;
};
toado queu[10000000];

void init(){
	front = 0;
	rear = 0;
}

void push(int xx, int yy) {
	queu[rear].x = xx;
	queu[rear].y = yy;
	rear ++;
}

toado pop() {
	toado t = queu[front];
	front ++;
	return t;
}

void BFS(int x, int y) {
	init();
	visit[x][y] = 1;
	push(x, y);
	while(front < rear) {
		toado t = pop();
		for(int i = 0; i < 8; i ++) {
			int xn = t.x + dx[i];
			int yn = t.y + dy[i];
			if(xn >= 0 && xn < hang && yn >= 0 && yn < cot) {
				if(visit[xn][yn] == 0) {
					push(xn, yn);
					visit[xn][yn] = visit[t.x][t.y] + 1;
				}
				else if (visit[t.x][t.y] + 1 < visit[xn][yn]) {
					push(xn, yn);
					visit[xn][yn] = visit[t.x][t.y] + 1;
				}
			}
		}
	}
}

void dequy(int dem, int n, int count = 0) {
	if(dem == sl-1) {
		if(rs > count) rs = count;
		return;
	}
	if(count > rs) return;
	
	for(int i = 1; i < sl; i ++) {
		if(vs[i] == 0 && kc[n][i] != 0) {
			vs[i] = 1;
			dequy(dem+1, i, count + kc[n][i]);
			vs[i] = 0;
		}
	}
}

int main()
{
	freopen("input.txt", "r", stdin);
	ios::sync_with_stdio(false);
	cin >> T;
	for(int test_case = 1; test_case <= T; test_case ++) {
		sl = 1;
		int check = 0;
		cin >> hang >> cot;
		for(int i = 0; i < hang; i ++) {
			for(int j = 0; j < cot; j ++) {
				visit[i][j] = 0;
				cin >> arr[i][j];
				if(arr[i][j] == 3) {
					vtdx = i;
					vtdy = j;
					dich[0][0] = i;
					dich[0][1] = j;
				}
				if (arr[i][j] == 1) {
					dich[sl][0] = i;
					dich[sl][1] = j;
					sl ++;
				}
			}
		}

		rs = 10000;
		for(int i = 0; i < sl; i ++) {
			for(int j = 0; j < hang; j ++) {
				for(int k = 0; k < cot; k ++) {
					visit[j][k] = 0;
				}
			}
			int x = dich[i][0];
			int y = dich[i][1];
			BFS(x, y);
			for(int j = 0; j < sl; j ++) {
				kc[i][j] = visit[dich[j][0]][dich[j][1]] - 1;
			}
		}

		//for(int i = 0; i < sl; i ++) {
		//	for(int j = 0; j < sl; j ++) {
		//		cout << kc[i][j] << " ";
		//	}
		//	cout << endl;
		//}
		//cout << endl << endl;
		//for(int i = 0; i < sl; i ++) {
		//	for(int j = 0; j < 2; j ++) {
		//		cout << dich[i][j] << " ";
		//	}
		//	cout << endl;
		//}
		for(int i = 0; i < sl; i ++) vs[i] = 0;
		vs[0] = 1;
		dequy(0,0,0);
		cout << "Case #" << test_case << endl << rs << endl;
	}
	return 0;
}