# princess code

unknown
plain_text
6 months ago
1.5 kB
3
Indexable
Never
```#include <iostream>
using namespace std;

int in1[201][201];
int in2[201][201];
int dem1[201][201];
int dem2[201][201];
int Qx[10000000];
int Qy[10000000];
int Qd[10000000];
int r = -1, f = -1;
int dx[4]= {1,0,0,-1};
int dy[4]= {0,1,-1,0};
void push(int x, int y, int d){
r++;
Qx[r] = x;
Qy[r] = y;
Qd[r] = d;
}
void pop(int &x, int &y, int &d){
f++;
x = Qx[f];
y = Qy[f];
d = Qd[f];
}

int BFS(int x, int y,int d,int a, int b, int n,int in[201][201], int dem[201][201]){
r = -1;
f= -1;
push(x,y,d);
while(r != f){
pop(x,y,d);
for(int i = 0; i < 4; i++){
int x1 = x + dx[i];
int y1 = y + dy[i];
if(x1 > 0 && x1 <= n && y1 > 0 && y1 <= n){
if(in[x1][y1] == 1 ){
push(x1,y1,d+1);
in[x1][y1] = 0;
if(d+1 < dem[x1][y1]){
dem[x1][y1] = d + 1;
}

}
else if(x1 == a && y1 == b ){
dem[x1][y1] = d + 1;
return dem[x1][y1];
}
}
}
}
return -1;
}
int main(){
int T;
cin >> T;
for(int tc = 1; tc <= T; tc++){
r = -1;
f= -1;
int n;
cin >> n;
int x,y;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
cin >> in1[i][j];
in2[i][j] = in1[i][j];
dem1[i][j] = dem2[i][j] = 1000000;
if(in1[i][j] == 2){
x = i;
y = j;
}
}
}
int d1 = BFS(1,1,0,x,y,n,in1,dem1);
int d2 = BFS(x,y,0,n,n,n,in2,dem2);
if(d1 == -1 || d2 == -1){
cout << -1 << endl;
}
else if (d1 != -1 && d2 != -1){
cout << d1 + d2 << endl;
}
}
return 0;
}```