# Untitled

unknown
plain_text
a year ago
1.9 kB
2
Indexable
Never
```#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;
}```