Untitled

mail@pastecode.io avatar
unknown
plain_text
13 days ago
1.9 kB
1
Indexable
Never
#include<iostream>

using namespace std;
int T, Answer, n, m, p, q, s, t, ri[201], ci[201], map[201][201], visited[201][201];

int dx[4] = {1, -1, -1, 1};
int dy[4] = {1, 1, -1, -1};
const int MAX = 101;
struct Queue
{
	int queue[MAX];
	int front, rear;
	Queue(){
		reset();
	}
	void reset(){
		front = -1;
		rear = -1;
	}

	void push(int value){
		queue[++rear % MAX] = value;
	}

	int pop(){
		return queue[++front % MAX];
	}

	bool isEmpty(){
		return front == rear;
	}
};

bool isValid(int x, int y){
	return x > 0 && x <= n && y > 0 && y <= n;
}


void bfs(int x, int y){
	Queue q;
	visited[x][y] = 1;
	q.push(x);
	q.push(y);

	while(!q.isEmpty()){
		int r = q.pop();
		int c = q.pop();
		for(int i = 0; i < 4; i++){
			for(int j = 1; j <= n; j++){
				int nx = r + j * dx[i];
				int ny = c + j * dy[i];
				
				if(map[nx][ny] == 1) break;
				else if(map[nx][ny] == 0 && isValid(nx, ny)){
					map[nx][ny] = map[r][c] + 1;
					q.push(nx);
					q.push(ny);
					if(s == nx && t == ny) return;
				}
			}

		}
	}
}

int main()
{
	//freopen("input.txt", "r", stdin);
	freopen("QuanTuong.txt", "r", stdin);

	cin >> T;

	for(int test_case = 1; test_case <= T; ++test_case)
	{
		Answer = 0;
		cin >> n >> m >> p >> q >> s >> t;

		for(int i = n; i >= 1; i--){
			for(int j = 1; j <= n; j++){
				map[i][j] = 0;
			}
		}
		map[p][q] = 2;
		for(int i = 1; i <= m; i++){
			cin >> ri[i] >> ci[i];
			map[ri[i]][ci[i]] = 1;
		}

		if(p == s && q == t){
			cout << 0 << endl;
		}
		else{
			bfs(p, q);
			if(map[s][t] == 0){
				cout << -1 << endl;
			}
			else cout << map[s][t] - 2 << endl;
			/*for(int i = n; i >= 1; i--){
				for(int j = 1; j <= n; j++){
					cout << map[i][j] << " ";
				}
				cout << endl;
			}*/
		}

	}
	return 0;//Your program should return 0 on normal termination.
}
Leave a Comment