Untitled

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;

#define MAXSIZE 101
#define MAXQUEUE 10100

class Queue
{
	int head, rear;
	int A[MAXQUEUE];
public:
	Queue();
	~Queue();
	void enQueue(int inS);
	int deQueue();
	bool is_Empty();
	void reset();

private:

};

Queue::Queue()
{
	head = rear = -1;
}

Queue::~Queue()
{
}

void Queue::enQueue(int inS) {
	A[++rear] = inS;
}

int Queue::deQueue() {
	return A[++head];
}

bool Queue::is_Empty() {
	if (head == rear) return true;
	return false;
}

void Queue::reset() {
	head = rear = -1;
}

int Map[101][101];
int visited[101][101];
int dist[11][11];
int rDirty[11], cDirty[11], node[11];
int nTestcase, N, M, nDirty, rStart, cStart, Min, step, cnt, nr, nc, rr, cc, sum;
int rspin[4] = { -1,1,0,0 };
int cspin[4] = { 0,0,-1,1 };
Queue rQueue, cQueue;

void resetVisit() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			visited[i][j] = -1;
		}
	}
}
int total() {
	int temp = 0;
	for (int i = 0; i < nDirty; i++) {
		temp += node[i];
	}
	return temp;
}

void backtrack(int dirty, int nD) {
	if (step >= Min)
		return;
	if (nD == nDirty) {
		Min = Min > step ? step : Min;
		return;
	}
	for (int i = 1; i < nDirty; i++) {
		if (dist[dirty][i] != 0 && node[i] == 0) {
			node[i]++;
			step += dist[dirty][i];
			backtrack(i, nD + 1);
			node[i]--;
			step -= dist[dirty][i];
		}
	}
}

void BFS(int r, int c) {
	cnt = 0;
	rQueue.reset();
	cQueue.reset();
	rQueue.enQueue(r);
	cQueue.enQueue(c);
	visited[r][c]++;
	while (rQueue.is_Empty() == false && cnt < nDirty + 1) {
		rr = rQueue.deQueue();
		cc = cQueue.deQueue();
		for (int i = 0; i < 4; i++) {
			nr = rr + rspin[i];
			nc = cc + cspin[i];
			if (nr >= 0 && nr < N && nc >= 0 && nc < M && Map[nr][nc] != 2) {
				if (visited[nr][nc] == -1) {
					if (Map[nr][nc] == 1)
						cnt++;
					visited[nr][nc] = visited[rr][cc] + 1;
					rQueue.enQueue(nr);
					cQueue.enQueue(nc);
				}
				else if (visited[nr][nc] > visited[rr][cc] + 1) {
					visited[nr][nc] = visited[rr][cc] + 1;
				}
			}
		}
	}
}


int main() {
	freopen("input.txt", "r", stdin);
	cin >> nTestcase;
	for (int testcase = 1; testcase <= nTestcase; testcase++) {
		cin >> N >> M;
		nDirty = 1;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				cin >> Map[i][j];
				visited[i][j] = -1;
				if (Map[i][j] == 1 || Map[i][j] == 3) {
					if (Map[i][j] == 1) {
						rDirty[nDirty] = i;
						cDirty[nDirty] = j;
						nDirty++;
					}
					else {
						rDirty[0] = i;
						cDirty[0] = j;
					}
				}

			}
		}
		bool check = true;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (Map[i][j] == 1 || Map[i][j] == 3) {
					int temp = 0;
					if ((i == 0 && j == 0) || (i == 0 && j == M - 1) || (i == N - 1 && j == 0) || (i == N - 1 && j == M - 1)) {
						for (int k = 0; k < 4; k++) {
							nr = i + rspin[k];
							nc = j + cspin[k];
							if (nr >= 0 && nr < N && nc >= 0 && nc < M && Map[nr][nc] == 2)
								temp++;
						}
						if (temp == 2)
							check = false;
						break;
					}
					else if (i == 0 || j == 0 || i == N - 1 || j == M - 1) {
						for (int k = 0; k < 4; k++) {
							nr = i + rspin[k];
							nc = j + cspin[k];
							if (nr >= 0 && nr < N && nc >= 0 && nc < M && Map[nr][nc] == 2)
								temp++;
						}
						if (temp == 3)
							check = false;
						break;
					}
					else {
						for (int k = 0; k < 4; k++) {
							nr = i + rspin[k];
							nc = j + cspin[k];
							if (nr >= 0 && nr < N && nc >= 0 && nc < M && Map[nr][nc] == 2)
								temp++;
						}
						if (temp == 4)
							check = false;
						break;
					}
				}
			}
		}
		if (check == false) {
			cout << "Case #" << testcase << endl << -1 << endl;
		}
		else {
			Min = 100000000; step = cnt = 0;
			check = true;
			for (int i = 0; i < nDirty; i++) {
				resetVisit();
				BFS(rDirty[i], cDirty[i]);
				for (int j = 0; j < nDirty; j++) {
					dist[i][j] = visited[rDirty[j]][cDirty[j]];
					if (dist[i][j] == -1) {
						check = false;
						break;
					}
				}
				node[i] = 0;
			}
			if (check == false) {
				cout << "Case #" << testcase << endl << -1 << endl;
			}
			else
			{
				node[0] = 1;
				backtrack(0, 1);
				cout << "Case #" << testcase << endl << Min << endl;
			}
		}
	}
	return 0;
}