Untitled

#include<iostream>
#define MAX_SIZE 1000

using namespace std;

int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};

int map[222][222];
int princessX;
int princessY;

bool visit[222][222];

int qx[MAX_SIZE];
int qy[MAX_SIZE];
int front = -1;
int rear = -1;

int ans;
int N; 

void push(int x, int y){
	rear++;
	qx[rear] = x;
	qy[rear] = y;
}

void pop(){
	front++;
}

bool isEmpty(){
	return front == rear;
}
	



int BFS(int x, int y, int desX, int desY){
	visit[x][y] = true;
	push(x, y);
	int dem = 0;
	while (!isEmpty()){
		pop();
		int x1 = qx[front];
		int y1 = qy[front];
		dem++;
		for (int i = 0; i < 4; i++){
			int x2 = x1 + dx[i];
			int y2 = y1 + dy[i];
			if ( map[x2][y2]>0 && visit[x2][y2] == false && x2>=1 && x2 <=N && y2>=1 && y2<=N){
				visit[x2][y2] = true;
				push(x2,y2);
				if (x2 == desX && y2 == desY){
					return dem;
				}
			}
		}
	}
	return 0;
}

void reset(){
	
	for (int i = 0; i < 222; i++) {
		for (int j = 0; j < 222; j++){
			visit[i][j] = false;
		}
	}
}

int main(){
	freopen("input.txt", "r", stdin);
	int TC; cin >> TC;
	for (int tc = 1; tc <= TC; tc++){
		cin >> N;
		for (int i = 1; i <= N; i++){
			for(int j = 1; j <= N; j++){				
				cin >> map[i][j];
				if(map[i][j] == 2) {
					princessX = i;
					princessY = j;
				}
			}
		}
		
		int k1 = 0, k2= 0;
		// reset
		reset();
		k1 = BFS(1,1,princessX,princessY);
		
		reset();
		k2 = BFS(N,N,princessX,princessY);


		if(k1==0 || k2 == 0) ans = -1;
		cout << k1+k2 << endl;
	}
	return 0;
}