Untitled

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
//Queue.h
#define MAX_QUEUE 100000
template<typename T>
class LinearQueue {
	T Q[MAX_QUEUE];
	int front;
	int rear;
public:
	LinearQueue()
	{
		front = rear = -1;
	}

	bool isEmpty()
	{
		return front == -1;
	}

	bool isFull()
	{
		return front == 0 && rear == MAX_QUEUE - 1;
	}

	T deQueue()
	{
		T ele = Q[front];
		if (!isEmpty())
		{
			//ele = Q[front];
			if (front >= rear)
			{
				front = -1;
				rear = -1;
			}
			else front++;
		}
		return ele;
	}

	void enQueue(T data)
	{
		if (!isFull())
		{
			if (front == -1) front++;
			rear++;
			Q[rear] = data;
		}
	}

	void reset()
	{
		front = rear = -1;
	}
	T head()
	{
		if (!isEmpty())
			return Q[front];
	}
	T tail()
	{
		if (!isEmpty())
			return Q[rear];
	}
	int size()
	{
		if (isEmpty()) return 0;
		else return rear - front + 1;
	}
};
//
#define MAX 105
#define MAX_P 12
#define INF 10000000
#define min(a, b) a < b ? a : b
int N, M, sr, sc;
int min_step, step;
int map[MAX][MAX];
int visited_map[MAX][MAX];
int R[MAX_P];
int C[MAX_P];
int adj[MAX_P][MAX_P];
int visited[MAX_P];
int Point;
int dr[4] = { 0, 0, 1, -1 };
int dc[4] = { 1, -1, 0, 0 };
LinearQueue<int> Q = LinearQueue<int>();
void resetMap()
{
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
		{
			visited_map[i][j] = 0;
		}
}
int BFS(int s, int e)
{
	int cr, cc, nr, nc;
	Q.reset();
	Q.enQueue(R[s]);
	Q.enQueue(C[s]);
	resetMap();
	visited_map[R[s]][C[s]] = 1;
	while (!Q.isEmpty())
	{
		cr = Q.deQueue();
		cc = Q.deQueue();
		for (int i = 0; i < 4; i++)
		{
			nr = cr + dr[i];
			nc = cc + dc[i];
			if (nr >= 0 && nr < N && nc >= 0 && nc < M && visited_map[nr][nc] == 0 && map[nr][nc] != 2)
			{
				Q.enQueue(nr);
				Q.enQueue(nc);
				visited_map[nr][nc] = visited_map[cr][cc] + 1;

				if (nr == R[e] && nc == C[e])
					return visited_map[nr][nc] - 1;
			}
		}
	}
	return -1;
}
bool isClean()
{
	for (int i = 1; i < Point; i++)
	{
		if (visited[i] == 0)
			return false;
	}
	return true;
}
void backtrack(int cur)
{
	if (step >= min_step)
		return;
	if (isClean())
	{
		min_step = min(min_step, step);
		return;
	}
	//int dis, new_step;
	for (int i = 1; i < Point; i++)
	{
		if (adj[cur][i] != -1)
		{
			if (visited[i] == 0)
			{
				visited[i] = 1;
				step += adj[cur][i];
				backtrack(i);
				visited[i] = 0;
				step -= adj[cur][i];
			}
		}
	}
}
int main()
{
	int tc;
	int T;
	freopen("input.txt", "r", stdin);
	cin >> T;
	for (tc = 1; tc <= T; ++tc)
	{
		cin >> N >> M;
		Point = 1;
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < M; j++)
			{
				cin >> map[i][j];
				if (map[i][j] == 3)
				{
					R[0] = i;
					C[0] = j;
				}
				if (map[i][j] == 1)
				{
					R[Point] = i;
					C[Point] = j;
					Point++;
				}
			}
		}
		for (int i = 0; i < Point; i++)
		{
			visited[i] = 0;
		}
		for (int i = 0; i < Point - 1; i++)
		{
			for (int j = i + 1; j < Point; j++)
			{
					adj[i][j] = BFS(i, j);
					adj[j][i] = adj[i][j];
			}
		}
		step = 0; min_step = INF;
		backtrack(0);
		min_step = (min_step == INF) ? -1 : min_step;
		cout << "Case #" << tc << endl;
		cout << min_step << endl;
	}
	return 0;
}