Untitled

#define _CRT_SECURE_NO_DEPRECATE
#include <iostream>
#define MAX_SIZE 1000
using namespace std;

// Implement Queue
class Queue {
private:
	int a[MAX_SIZE];
	int front;
	int rear;
public:
	Queue() {
		front = -1;
		rear = -1;
	}

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

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

	void enQueue(int x) {
		if (isFull()) {
			cout << "Queue is full" << endl;
		}
		else {
			if (front == -1) front = 0;
			a[++rear] = x;
		}
	}

	int deQueue() {
		if (isEmpty()) {
			cout << "Queue is empty" << endl;
			return -1;
		}
		else {
			int x = a[front];
			if (front >= rear) {
				front = -1;
				rear = -1;
			}
			else {
				front++;
			}
			return x;
		}
	}

	void display() {
		for (int i = front; i <= rear; i++) {
			cout << a[i] << endl;
		}
	}
};

// Princess
int N;
int dx[] = { 1,-1, 0, 0 };
int dy[] = { 0, 0, 1,-1 };
int p[200][200] = { 0 };
int visited[200][200] = { 0 };
int cnt[200][200] = { 0 }; // Dem duong di ngan nhat

int BFS(int x, int y, int a, int b) {
	bool isFind = false;
	Queue qx, qy;
	qx.enQueue(x);
	qy.enQueue(y);
	visited[x][y] = 1;

	// cout << x << " " << y << endl;

	while (!qx.isEmpty() && !qy.isEmpty()) {
		int topx = qx.deQueue();
		int topy = qy.deQueue();

		for (int k = 0; k < 4; k++) {
			int x1 = topx + dx[k];
			int y1 = topy + dy[k];

			if (x1 >= 0 && x1 < N && y1 >= 0 && y1 < N && p[x1][y1] != 0 && visited[x1][y1] != 1) {
				// cout << x1 << " " << y1 << endl;

				cnt[x1][y1] = cnt[topx][topy] + 1;
				visited[x1][y1] = 1;

				if (x1 == a && y1 == b) {
					return cnt[a][b];
				}

				qx.enQueue(x1);
				qy.enQueue(y1);
			}
		}
	}

	return -1;
}

void reset() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cnt[i][j] = 0;
			visited[i][j] = 0;
		}
	}
}

int main() {
	freopen("input.txt", "r", stdin);
	int T; cin >> T;

	for (int tc = 1; tc <= T; tc++) {
		cin >> N;
		int xPrincess, yPrincess;

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				cin >> p[i][j];
				if (p[i][j] == 2) {
					xPrincess = i;
					yPrincess = j;
				}
			}
		}

		reset();
		int d1 = BFS(xPrincess, yPrincess, 0, 0);
		reset();
		int d2 = BFS(xPrincess, yPrincess, N - 1, N - 1);

		cout << (d1 == -1 || d2 == -1 ? -1 : d1 + d2) << endl;
	}

	return 0;
}