Untitled

Lv3. Princess
Ma trận NxN (N <= 200). có các giá trị: 0, 1, 2.
Xuất phát từ (1,1), Ơm đường ngắn nhất đến 2.
Sau đó, Ơm đường ngắn nhất từ 2 đến (N,N).
*/ Input
- số test case (t<=10)
- nhập N
- nhập ma trận NxN
*/ Output: gồm t dòng
in ra số bước nhảy or in ra -1 nếu ko Ơm đc đường
**/ test
2
5
1 0 1 1 0
1 0 0 0 0
1 1 2 1 1
1 1 1 0 1
1 0 1 0 1
6
1 1 0 2 1 1
0 1 0 1 0 1
0 1 0 1 0 1
0 0 0 1 0 1
0 0 0 1 0 1
1 1 1 1 0 1
==>
8
-1
************************
#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 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(){
	front = -1;
	rear = -1;
	for (int i = 0; i < 222; i++) {
		for (int j = 0; j < 222; j++){
			visit[i][j] = false;
		}
	}
}

int main(){
	freopen("test.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) cout << -1 << endl;
		else cout << k1+k2 << endl;
	}
	return 0;
}