Untitled

Xét bàn cờ vuông kích thước n×n. Các dòng được đánh số từ 1 đến n, từ dưới lên trên. Các cột được đánh số từ 1 đến n từ trái qua phải.

Ô nằm trên giao của dòng i và cột j được gọi là ô (i,j). Trên bàn cờ có m (0 ≤ m ≤ n) quân cờ. Với m > 0, quân cờ thứ i ở ô (ri, ci), i = 1,2,..., m. Không có hai quân cờ nào ở trên cùng một ô. Trong số các ô còn lại của bàn cờ, tại ô (p, q) có một quân tượng. Mỗi một nước đi, từ vị trí đang đứng quân tượng chỉ có thể di chuyển đến được những ô trên cùng đường chéo với nó mà trên đường đi không phải qua các ô đã có quân

Cần phải đưa quân tượng từ ô xuất phát (p, q) về ô đích (s,t).

Cho kích thước bàn cờ n, số quân cờ hiện có trên bàn cờ m và vị trí của chúng, ô xuất phát và ô đích của quân tượng. Hãy xác định số nước đi ít nhất cần thực hiện để đưa quân tượng về ô đích hoặc đưa ra số -1 nếu điều này không thể thực hiện được.

 

 

Constraints

N = 1~200

 

Input

Dòng đầu tiên chứa số testcase. Mỗi testcase có cấu trúc như sau:

Dòng thứ nhất chứa 6 số nguyên n, m, p, q, s, t.

Nếu m > 0 thì mỗi dòng thứ i trong m dòng tiếp theo chứa một cặp số nguyên ri , ci xác định vị trí quân thứ i.

Hai số liên tiếp trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.

 

Output

Với mỗi test case in ra 1 dòng duy nhất là số nước đi tìm được.

 

Sample

 

Input

2

5 5 5 5 5 3
1 2
1 5
2 2
4 2
4 3

8 3 7 2 1 4

5 4

3 4

4 7

 

Output

2

3

#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(!isValid(nx, ny)||map[nx][ny] == 1) break;
				else if(map[nx][ny] == 0 ){
					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.
}