Untitled

//The Knight
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
#define MAX_QUEUE 1000000
template<typename T>
class Queue {
	T Q[MAX_QUEUE];
	int front;
	int rear;
public:
	Queue()
	{
		front = rear = -1;
	}
	bool isEmpty()
	{
		return front == -1;
	}
	bool isFull()
	{
		return front == 0 && rear == MAX_QUEUE - 1;
	}
	int size()
	{
		if (isEmpty())
			return 0;
		else return rear - front + 1;
	}
	void enQueue(T data)
	{
		if (!isFull())
		{
			if (front == -1) front++;
			rear++;
			Q[rear] = data;
		}
	}
	T deQueue()
	{
		T element;
		if (!isEmpty())
		{
			element = Q[front];
			if (front >= rear)
			{
				reset();
			}
			else front++;
			return element;
		}
	}
	void reset()
	{
		front = rear = -1;
	}
	T head()
	{
		return Q[front];
	}
	T tail()
	{
		return Q[rear];
	}
};
#define MAX 100
#define MAX_P 20
#define INF 10000000
int M, N, Point, step, min_step;
int map[MAX][MAX];
int visited[MAX][MAX];
int visited_point[MAX_P];
int adj[MAX_P][MAX_P];
int dr[8] = {-1, -2, -2, -1, 1, 2, 2, 1};
int dc[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int R[MAX_P];
int C[MAX_P];
Queue<int> Q = Queue<int>();
void resetVisited()
{
	for(int i = 0; i < M; i++)
		for (int j = 0; j < N; j++)
		{
			visited[i][j] = 0;
		}
}

int BFS(int s, int e)
{
	int nr, nc, cr, cc;
	Q.reset();
	resetVisited();
	Q.enQueue(R[s]);
	Q.enQueue(C[s]);
	visited[R[s]][C[s]] = 1;
	while (!Q.isEmpty())
	{
		cr = Q.deQueue();
		cc = Q.deQueue();
		for (int i = 0; i < 8; i++)
		{
			nr = cr + dr[i];
			nc = cc + dc[i];
			if (nr >= 0 && nr < M && nc >= 0 && nc < N && visited[nr][nc] == 0)
			{
				Q.enQueue(nr);
				Q.enQueue(nc);
				visited[nr][nc] = visited[cr][cc] + 1;
				if (nr == R[e] && nc == C[e])
					return visited[nr][nc] - 1;
			}
		}
	}
	return -1;
}
void backtrack(int k, int prev)
{
	if (step >= min_step)
		return;
	if (k == Point)
	{
		min_step = step < min_step ? step : min_step;
		return;
	}
	for (int i = 1; i < Point; i++)
	{
		if (visited_point[i] == 0)
		{
			visited_point[i] = 1;
			step += adj[prev][i];
			backtrack(k + 1, i);
			step -= adj[i][prev];
			visited_point[i] = 0;
		}
	}
}
int main()
{
	int tc, T;
	freopen("input.txt", "r", stdin);
	cin >> T;
	for (tc = 1; tc <= T; tc++)
	{
		cin >> M >> N;
		Point = 1;
		//read input
		for (int i = 0; i < M; i++)
		{
			for (int j = 0; j < N; 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++;
				}
			}
		}
		//adjacent matrix
		for (int i = 0; i < Point; i++)
		{
			visited_point[i] = 0;
			for (int j = i; j < Point; j++)
			{
				if (j == i)
					adj[i][j] = 0;
				else
				{
					adj[i][j] = adj[j][i] = BFS(i, j);
				}
			}
		}
		step = 0; min_step = INF;
		backtrack(1, 0);
		cout << "Case #" << tc << endl;
		cout << min_step << endl;
	}
	return 0;
}



// The crazy King
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#define MAX_QUEUE 1000000
template<typename T>
class Queue {
	T Q[MAX_QUEUE];
	int front;
	int rear;
public:
	Queue()
	{
		front = rear = -1;
	}
	bool isEmpty()
	{
		return front == -1;
	}
	bool isFull()
	{
		return front == 0 && rear == MAX_QUEUE - 1;
	}
	int size()
	{
		if (isEmpty())
			return 0;
		else return rear - front + 1;
	}
	void enQueue(T data)
	{
		if (!isFull())
		{
			if (front == -1) front++;
			rear++;
			Q[rear] = data;
		}
	}
	T deQueue()
	{
		T element;
		if (!isEmpty())
		{
			element = Q[front];
			if (front >= rear)
			{
				reset();
			}
			else front++;
			return element;
		}
	}
	void reset()
	{
		front = rear = -1;
	}
	T head()
	{
		return Q[front];
	}
	T tail()
	{
		return Q[rear];
	}
};
using namespace std;
#define MAX 105
int M, N, sr, sc, er, ec, ans;
char map[MAX][MAX];
int visited[MAX][MAX];
int drH[8] = { -1, -2, -2, -1, 1, 2, 2, 1 };
int dcH[8] = { -2, -1, 1, 2, 2, 1, -1, -2 };
int drK[8] = { 0, 0, 1, -1, -1, -1, 1, 1 };
int dcK[8] = { 1, -1, 0, 0, -1, 1, -1, 1 };
Queue<int> Q = Queue<int>();
void marking(int r, int c)
{
	int nr, nc;
	visited[r][c] = -1;
	for (int i = 0; i < 8; i++)
	{
		nr = r + drH[i];
		nc = c + dcH[i];
		if (nr >= 0 && nr < M && nc >= 0 && nc < N)
			visited[nr][nc] = -1;
	}
}
int main()
{
	int tc, T, cr, cc, nr, nc;
	freopen("input.txt", "r", stdin);
	cin >> T;
	for (tc = 1; tc <= T; tc++)
	{
		cin >> M >> N;
		for (int i = 0; i < M; i++)
			for (int j = 0; j < N; j++)
				visited[i][j] = 0;
		for (int i = 0; i < M; i++)
		{
			for (int j = 0; j < N; j++)
			{
				cin >> map[i][j];
				if (map[i][j] == 'A')
				{
					sr = i;
					sc = j;
				}
				else if (map[i][j] == 'B')
				{
					er = i;
					ec = j;
				}
				else if (map[i][j] == 'Z')
					marking(i, j);
			}
		}
		ans = -1;
		Q.reset();
		Q.enQueue(sr);
		Q.enQueue(sc);
		visited[sr][sc] = 1; 
		visited[er][ec] = 0;
		while (!Q.isEmpty())
		{
			cr = Q.deQueue();
			cc = Q.deQueue();
			for (int i = 0; i < 8; i++)
			{
				nr = cr + drK[i];
				nc = cc + dcK[i];
				if (nr >= 0 && nr < M && nc >= 0 && nc < N && visited[nr][nc] == 0)
				{
					Q.enQueue(nr);
					Q.enQueue(nc);
					visited[nr][nc] = visited[cr][cc] + 1;

					if (nr == er && nc == ec)
					{
						ans = visited[nr][nc] - 1;
						goto end;
					}
				}
			}
		}
	end:
		cout << ans << endl;
	}
	return 0;
}