Untitled

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

#define MAXQUEUE 11000

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 chess[101][101];
int visited[101][101];
int dist[101][101];
int rTarget[101], cTarget[101], node[101];
int nTestcase, N, M, rStart, cStart, rr, cc, nr, nc, nTarget, cnt, Min, step;
int rspin[8] = { -2,-1,1,2,2,1,-1,-2 };
int cspin[8] = { -1,-2,-2,-1,1,2,2,1 };
Queue rQueue, cQueue;

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

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 < nTarget) {
		rr = rQueue.deQueue();
		cc = cQueue.deQueue();
		for (int i = 0; i < 8; i++) {
			nr = rr + rspin[i];
			nc = cc + cspin[i];
			if (nr >= 0 && nr < N && nc >= 0 && nc < M) {
				if (visited[nr][nc] == -1) {
					if (chess[nr][nc] != 0) {
						cnt++;
					}
					rQueue.enQueue(nr);
					cQueue.enQueue(nc);
					visited[nr][nc] = visited[rr][cc] + 1;
				}
				else if (visited[nr][nc] > visited[rr][cc] + 1) {
					visited[nr][nc] = visited[rr][cc] + 1;
				}
			}
		}
	}
}

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

int main() {
	freopen("input.txt", "r", stdin);
	cin >> nTestcase;
	for (int testcase = 1; testcase <= nTestcase; testcase++) {
		cin >> N >> M;
		nTarget = 1;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				cin >> chess[i][j];
				if (chess[i][j] == 3) {
					rTarget[0] = i;
					cTarget[0] = j;
				}
				else if (chess[i][j] == 1) {
					rTarget[nTarget] = i;
					cTarget[nTarget] = j;
					nTarget++;
				}
			}
		}
		for (int i = 0; i < nTarget; i++) {
			resetVisit();
			BFS(rTarget[i],cTarget[i]);
			for (int j = 0; j < nTarget; j++) {
				dist[i][j] = visited[rTarget[j]][cTarget[j]];
			}
			node[i] = 0;
		}
		node[0] = 1;
		Min = 100000000;
		step = 0;
		backtrack(0, 1);
		cout << "Case #" << testcase << endl << Min << endl;
	}
	return 0;
}