Untitled

#include <iostream>
using namespace std;
int T;
int m, n, map[100][100], visit[100][100];
int dirty[100][2], top, xst, yst, numDirty, visitDirty[100], indexCur;
int matrix[100][100], minDis, possible;

int tmpx, tmpy, tx, ty, front, rear, qx[10000], qy[10000];
void initQueue() {
	front = rear = -1;
}
int isEmpty() {
	return front == rear;
}
void enQueue(int x, int y)
{
	qx[++rear] = x;
	qy[rear] = y;
}
void deQueue(int &tmpx, int &tmpy) {
	tmpx = qx[++front];
	tmpy = qy[front];
}
int isValid() {
	return tx >= 0 && tx < n && ty >= 0 && ty < m && map[tx][ty] != 2;
}
void resetVisit() {
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			visit[i][j] = 0;
}

int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, 1, 0, -1 };
int BFS(int x1, int y1, int x2, int y2) {
	int disMin = 1000000;
	int check = 0;
	resetVisit();
	initQueue();
	visit[x1][y1] = 1;
	enQueue(x1, y1);
	while (!isEmpty()) {
		deQueue(tmpx, tmpy);
		if (tmpx == x2 && tmpy == y2) {
			check = 1;
			disMin = visit[tmpx][tmpy] < disMin ? visit[tmpx][tmpy] : disMin;
		}
		for (int k = 0; k < 4; k++) {
			tx = tmpx + dx[k];
			ty = tmpy + dy[k];
			if (isValid()) {
				if (!visit[tx][ty] || (visit[tx][ty] && visit[tmpx][tmpy] + 1 < visit[tx][ty])) {
					visit[tx][ty] = visit[tmpx][tmpy] + 1;
					enQueue(tx, ty);
				}
			}
		}
	}
	if (check)
		return disMin - 1;
	else
		return -1;
}

void backtrack(int x, int y, int numClean, int dist) {
	if (dist > minDis)
		return;
	if (numClean == numDirty) {
		if (dist < minDis)
			minDis = dist;
		return;
	}

	for (int i = 0; i <= numDirty; i++) {
		if (dirty[i][0] == x && dirty[i][1] == y)
			indexCur = i;
	}

	for (int i = 0; i < numDirty; i++) {
		if (!visitDirty[i]) {
			visitDirty[i] = 1;
			backtrack(dirty[i][0], dirty[i][1], numClean + 1, dist + matrix[indexCur][i]);
			visitDirty[i] = 0;
		}
	}
}

int main() {
	cin >> T;
	for (int tc = 1; tc <= T; tc++) {
		top = -1;
		numDirty = 0;
		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) {
					xst = i;
					yst = j;
				}
				else if (map[i][j] == 1) {
					dirty[++top][0] = i;
					dirty[top][1] = j;
					numDirty++;
				}
			}
		}
		//Logic
		//Set up matrix ke
		dirty[++top][0] = xst;
		dirty[top][1] = yst;
		possible = 1;
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
				matrix[i][j] = 0;

		int distance, x1, y1, x2, y2;
		for (int i = 0; i <= numDirty; i++) {
			x1 = dirty[i][0];
			y1 = dirty[i][1];
			for (int j = i + 1; j <= numDirty; j++) {
				x2 = dirty[j][0];
				y2 = dirty[j][1];
				distance = BFS(x1, y1, x2, y2);
				if (distance == -1) possible = 0;
				matrix[i][j] = matrix[j][i] = distance;
				//cout << "X1:" << x1 << " " << "Y1:" << y1 << " " << "X2:" << x2 << " " << "Y2:" << y2 << " " << distance << endl;
			}
		}

		//Backtrack
		//Set up visitDirty
		for (int i = 0; i <= numDirty; i++) {
			visitDirty[i] = 0;
		}
		cout << "Case #"<<tc<<endl;
		if (possible) {
			minDis = 1000000;
			backtrack(xst, yst, 0, 0);
			cout << minDis << endl;
		}
		else {
			cout << -1 << endl;
		}
	}
	
	
	return 0;
}