# Untitled

unknown
plain_text
a year ago
2.4 kB
5
Indexable
Never
```#define _CRT_SECURE_NO_DEPRECATE
#include <iostream>
#define MAX_SIZE 1000
using namespace std;

// Implement Queue
class Queue {
private:
int a[MAX_SIZE];
int front;
int rear;
public:
Queue() {
front = -1;
rear = -1;
}

bool isFull() {
return front == 0 && rear == MAX_SIZE - 1;
}

bool isEmpty() {
return front == -1;
}

void enQueue(int x) {
if (isFull()) {
cout << "Queue is full" << endl;
}
else {
if (front == -1) front = 0;
a[++rear] = x;
}
}

int deQueue() {
if (isEmpty()) {
cout << "Queue is empty" << endl;
return -1;
}
else {
int x = a[front];
if (front >= rear) {
front = -1;
rear = -1;
}
else {
front++;
}
return x;
}
}

void display() {
for (int i = front; i <= rear; i++) {
cout << a[i] << endl;
}
}
};

// Princess
int N;
int dx[] = { 1,-1, 0, 0 };
int dy[] = { 0, 0, 1,-1 };
int p[200][200] = { 0 };
int visited[200][200] = { 0 };
int cnt[200][200] = { 0 }; // Dem duong di ngan nhat

int BFS(int x, int y, int a, int b) {
bool isFind = false;
Queue qx, qy;
qx.enQueue(x);
qy.enQueue(y);
visited[x][y] = 1;

// cout << x << " " << y << endl;

while (!qx.isEmpty() && !qy.isEmpty()) {
int topx = qx.deQueue();
int topy = qy.deQueue();

for (int k = 0; k < 4; k++) {
int x1 = topx + dx[k];
int y1 = topy + dy[k];

if (x1 >= 0 && x1 < N && y1 >= 0 && y1 < N && p[x1][y1] != 0 && visited[x1][y1] != 1) {
// cout << x1 << " " << y1 << endl;

cnt[x1][y1] = cnt[topx][topy] + 1;
visited[x1][y1] = 1;

if (x1 == a && y1 == b) {
return cnt[a][b];
}

qx.enQueue(x1);
qy.enQueue(y1);
}
}
}

return -1;
}

void reset() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cnt[i][j] = 0;
visited[i][j] = 0;
}
}
}

int main() {
freopen("input.txt", "r", stdin);
int T; cin >> T;

for (int tc = 1; tc <= T; tc++) {
cin >> N;
int xPrincess, yPrincess;

for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> p[i][j];
if (p[i][j] == 2) {
xPrincess = i;
yPrincess = j;
}
}
}

reset();
int d1 = BFS(xPrincess, yPrincess, 0, 0);
reset();
int d2 = BFS(xPrincess, yPrincess, N - 1, N - 1);

cout << (d1 == -1 || d2 == -1 ? -1 : d1 + d2) << endl;
}

return 0;
}```