Untitled

#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];
			/*sum = total();
			if(sum == nDirty){
				Min = Min > step ? step : Min;
				node[i]--;
				step -= dist[dirty][i];
				return;
			}*/
			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){
					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;
			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]];
				}
				node[i] = 0;
			}
			node[0] = 1;
			backtrack(0,1);
			cout << "Case #" << testcase << endl << Min << endl;
		}
	}
	return 0;
}