Untitled

PRINCESS

#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 };

int BFS(int x, int y) {
	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 (p[x1][y1] == 2) isFind = true;
				if (x1 == N - 1 && y1 == N - 1 && isFind == true) {
					return cnt[4][4];
				}

				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;

		 for (int i = 0; i < N; i++) {
			 for (int j = 0; j < N; j++) {
				 cin >> p[i][j];
			 }
		 }
		 reset();
		 cout << BFS(0, 0) << endl;
	}

	return 0;
}