Untitled

#include<iostream>
#define MAX_SIZE 1000
#define MAX_Q 1000000

using namespace std;

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

int map[MAX_SIZE][MAX_SIZE];
int princessX;
int princessY;
int cnt[MAX_SIZE][MAX_SIZE];

bool visit[MAX_SIZE][MAX_SIZE];

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

int ans;
int N; 

void enQueue(int x, int y){
	if(front == -1) front = 0;
	rear++;
	qx[rear] = x;
	qy[rear] = y;
}

void deQueue(){
	if(front >= rear){
		front = -1;
		rear = -1;
	}
	else front++;
}

bool isEmpty(){
	return front == -1;
}
	
int BFS(int x, int y, int desX, int desY){
	visit[x][y] = true;
	enQueue(x, y);
	while (!isEmpty()){
		int topx = qx[front];
		int topy = qy[front];
		deQueue();
		for (int i = 0; i < 4; i++){
			int x2 = topx + dx[i];
			int y2 = topy + dy[i];
			if ( map[x2][y2]>0 && visit[x2][y2] == false && x2>=1 && x2<=N && y2>=1 && y2<=N){
				visit[x2][y2] = true;
				cnt[x2][y2] = cnt[topx][topy] +1;
				if (x2 == desX && y2 == desY){
					return cnt[x2][y2];
				}
				enQueue(x2,y2);
			}
		}
	}
	return -1;
}

void reset(){
	front = -1;
	rear = -1;
	for (int i = 0; i < MAX_SIZE; i++) {
		for (int j = 0; j < MAX_SIZE; j++){
			visit[i][j] = false;
			cnt[i][j]=0;
		}
	}
}

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(princessX, princessY, 1,1);
		
		reset();
		k2 = BFS(princessX, princessY, N,N);


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