Share your repls and programming experiences

← Back to all posts
Quan Tuong
nhanbui19 (0)

#include <iostream>
#define MAX 200
#define M 40000
using namespace std;

int banCo[MAX+10]; // gia tri 1 la co vat can
int n; // kich thuoc ban co
int m; // so quan co da co tren ban co
int p, q; // vi tri bat dau cua quan tuong
int s, t; // vi tri dich cua quan tuong
int qR[M];
int qC[M];
int soBuoc[M];
int r[4] = {1, 1, -1, -1};
int c[4] = {1, -1, 1, -1};
int kt[4] = {1, 1, 1, 1};

int bfs(){
int dau = -1;
int cuoi = 0;
qR[0] = p;
qC[0] = q;
banCo[p] = 2;
soBuoc[0] = 0;
bool exist = false;
while (dau < cuoi){
for (int i = 0; i < 4; i++)
kt[i] = 1;
dau++;
int rCurrent = qR[dau];
int cCurrent = qC[dau];
for (int j = 1; j < n; j++){
for (int i = 0; i < 4; i++){
if (kt[i] == 0)
continue;
int rNext = rCurrent + r[i]j;
int cNext = cCurrent + c[i]
j;
if (rNext > 0 && rNext <= n && cNext > 0 && cNext <= n){
if (banCo[rNext] == 0){
cuoi++;
soBuoc[cuoi] = soBuoc[dau] + 1;
//track[cuoi] = dau;
if (rNext == s && cNext == t){
exist = true;
dau = cuoi;
j = n;
break;
}

					qR[cuoi] = rNext;
					qC[cuoi] = cNext;
					banCo[rNext][cNext] = 2;
				} else if (banCo[rNext][cNext] == 1){
					kt[i] = 0;
				}

			} 


		}
	}
}
if (!exist)
	return -1;
return exist?soBuoc[cuoi]:-1;

}

int main(){
ios::sync_with_stdio(false);
freopen("input.txt", "r", stdin);
int nTest;
cin >> nTest;
for (int iTest = 0; iTest < nTest; iTest++){

	cin >> n >> m >> p >> q >> s >> t;
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= n; j++){
			banCo[i][j] = 0;
		}
	}
	for (int i = 0; i < m; i++){
		int tmpR, tmpC;
		cin >> tmpR >> tmpC;
		banCo[tmpR][tmpC] = 1;
	}
	cout << bfs() << endl;

}
fclose(stdin);
return 0;

}