quan tuong

mail@pastecode.io avatar
unknown
plain_text
a year ago
1.7 kB
1
Indexable
Never
package day21_2706;

import java.util.Scanner;

public class quan_tuong_v2 {
	
	static int n, m, sx, sy, ex, ey;
	static int[][] map, visit;
	static int[][] d = {{-1, -1}, {-1, 1}, {1, 1}, {1, -1}};
	
	private static void BFS(){
		MyQueue qx = new MyQueue(n * n);
		MyQueue qy = new MyQueue(n * n);
		qx.enqueue(sx); qy.enqueue(sy);
		
		int x, y, dx, dy;
		while(!qx.isEmpty()){
			x = qx.dequeue(); y = qy.dequeue();
			for(int i = 0; i < 4; i++){
				dx = x + d[i][0]; dy = y + d[i][1];
				while(dx >= 0 && dy >= 0 && dx < n && dy < n && map[dx][dy] != -1){
					if(map[dx][dy] == Integer.MAX_VALUE){
						map[dx][dy] = map[x][y] + 1;
						qx.enqueue(dx); qy.enqueue(dy);
					}
					if(dx == ex && dy == ey) return;
					dx = dx + d[i][0]; dy = dy + d[i][1];
				}
			}
		}
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		Scanner sc = new Scanner(System.in);
		int testcase = sc.nextInt();
		for(int tc = 1; tc <= testcase; tc++){
			n = sc.nextInt(); m = sc.nextInt();
			sx = sc.nextInt(); sx = n - sx;
			sy = sc.nextInt() - 1;
			ex = sc.nextInt(); ex = n - ex;
			ey = sc.nextInt() - 1;
			
			map = new int[n][n];
			
			for(int i = 0; i < n; i++){
				for(int j = 0; j < n; j++){
					map[i][j] = Integer.MAX_VALUE;
				}
			}
			
			int a, b;
			for(int i = 0; i < m; i++){
				a = sc.nextInt(); b = sc.nextInt();
				map[n - a][b - 1] = -1;
			}
			
//			for(int i = 0; i < n; i++){
//				for(int j = 0; j < n; j++){
//					visit[i][j] = -1;
//				}
//			}
			map[sx][sy] = 0;
			BFS();
			if(map[ex][ey] == Integer.MAX_VALUE) System.out.println(-1);
			else System.out.println(map[ex][ey]);
			
		}
		
	}

}