Untitled

//Domino
#include <iostream>
using namespace std;
int m = 7, n = 8, res = 0;
int a[7][8];
bool vt[7][8];
bool used[7][8];

void reset() {
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < m; j++) {
			vt[i][j] = false;
			used[i][j] = false;
		}
	}
}

void backtrack(int k) {
	if (k == m * n) {
		res++;
		return;
	}
	int r = k / n;
	int c = k % n;
	if (!vt[r][c]) {
		if (c < 7) {
			int x = a[r][c];
			int y = a[r][c+1];
			if (!used[x][y] && !used[y][x]) {
				used[x][y] = used[y][x] = true;
				vt[r][c] = vt[r][c + 1] = true;
				backtrack(k + 2);
				used[x][y] = used[y][x] = false;
				vt[r][c] = vt[r][c + 1] = false;
			}
		}
		if (r < 6 && c < 8) {
			int x = a[r][c];
			int y = a[r+1][c];
			if (!used[x][y] && !used[y][x]) {
				used[x][y] = used[y][x] = true;
				vt[r][c] = vt[r+1][c] = true;
				backtrack(k + 1);
				used[x][y] = used[y][x] = false;
				vt[r][c] = vt[r + 1][c] = false;
			}
		}
	}
	else {
		backtrack(k + 1);
	}
}

void solve(int index) {
	res = 0;
	reset();
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			cin >> a[i][j];
		}
	}
	backtrack(0);
	cout << res << endl;
}

int main() {
	int t;
	cin >> t;
	for (int i = 1; i <= t; i++) {
		solve(i);
	}
}

//Crazy King
#include <iostream>
using namespace std;
int m, n, a[101][101], ax, ay, bx, by;
char b[101][101];
bool vt[101][101];
int rspin[] = {-1, -2, -1, -2, 1, 2, 1, 2};
int cspin[] = {-2, -1, 2, 1, -2, -1, 2, 1};

int krspin[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int kcspin[] = {-1, 0, 1, -1, 1, -1, 0, 1};

const int SIZE = 100000;

struct Point {
	int x, y;
};

template <typename T>
class Queue {
	int front, rear;
	T data[SIZE];
public:
	Queue() {
		front = rear = -1;
	}
	bool isFull() {
		return (front == 0 && rear == SIZE - 1) || (front == rear + 1);
	}
	bool isEmpty() {
		return front == -1;
	}
	void reset() {
		front = rear = -1;
	}
	void enQueue(T val) {
		if (!isFull()) {
			if (front == -1)	front++;
			rear = (rear + 1) % SIZE;
			data[rear] = val;
		}
	}
	T deQueue() {
		if (!isEmpty()) {
			T element = data[front];
			if (front == rear) {
				reset();
			}
			else {
				front = (front + 1) % SIZE;
			}
			return element;
		}
	}
};

Queue<Point> q;

void reset() {
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			a[i][j] = 0;
			vt[i][j] = false;
		}
	}
}

void solve(int index) {
	bool isGoal = true;
	reset();
	cin >> m >> n;
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			cin >> b[i][j];
			if (b[i][j] == 'A') {
				ax = i;
				ay = j;
			}
			if (b[i][j] == 'B') {
				bx = i;
				by = j;
			}
			if (b[i][j] == 'Z') {
				vt[i][j] = true;
				for (int k = 0; k < 8; k++) {
					int x = i + rspin[k];
					int y = j + cspin[k];
					if (x >= 0 && y >= 0 && x < m && y < n) {
						vt[x][y] = true;
						if (x == bx && y == by) {
							isGoal = false;
						}
					}
				}
			}
		}
	}
	int length = 0;
	q.reset();
	vt[ax][ay] = true;
	for (int i = 0; i < 8; i++) {
		int x = ax + krspin[i];
		int y = ay + kcspin[i];
		if (x == bx && y == by) {
			length = 1;
			break;
		}
		if (x >= 0 && y >= 0 && x < m && y < n && !vt[x][y]) {
			Point temp = { x, y };
			a[x][y] = a[ax][ay] + 1;
			q.enQueue(temp);
			vt[x][y] = true;
		}
	}
	if (length > 0) {
		cout << "Minimal possible length of a trip is 1\n";
	}
	else {
		while (!q.isEmpty()) {
			Point cur = q.deQueue();
			for (int i = 0; i < 8; i++) {
				int x = cur.x + krspin[i];
				int y = cur.y + kcspin[i];
				if (x >= 0 && y >= 0 && x < m && y < n && !vt[x][y]) {
					Point temp = { x, y };
					a[x][y] = a[cur.x][cur.y] + 1;
					q.enQueue(temp);
					vt[x][y] = true;
				}
			}
		}
		if (a[bx][by] == 0)
			cout << "King Peter, you can't go now!\n";
		else
			cout << "Minimal possible length of a trip is " << a[bx][by] << endl;
	}
	/*
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			cout << vt[i][j] << " ";
		}
		cout << endl;
	}*/
}

int main() {
	int t;
	cin >> t;
	for (int i = 1; i <= t; i++) {
		solve(i);
	}
}