Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
32 kB
8
Indexable
Never
//Quan Ma~



import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Solution {
	static int N, M, ans, quan;
	static int[][] map;
	static int[][] mapDinh;
	static int[][] danhSach;
	static int[][] vis;
	static int[] visDem;
	static int[] dx = { -2, -1, 1, 2, 2, 1, -1, -2 };
	static int[] dy = { 1, 2, 2, 1, -1, -2, -2, -1 };
	static MyQueue myQx = new MyQueue(100000);
	static MyQueue myQy = new MyQueue(100000);
	static MyQueue myQd = new MyQueue(100000);

	public static void main(String[] args) {

		try {
			System.setIn(new FileInputStream("input.txt"));
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}

		Scanner sc = new Scanner(System.in);

		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			ans = 999999;

			N = sc.nextInt();
			M = sc.nextInt();
			map = new int[N][M];
			vis = new int[N][M];

			danhSach = new int[N * M][2];
			int a = 0, b = 0;
			quan = 0;
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					map[i][j] = sc.nextInt();
					if (map[i][j] == 3) {
						danhSach[0][0] = i;
						danhSach[0][1] = j;
					}
					if (map[i][j] == 1) {
						quan++;
						danhSach[quan][0] = i;
						danhSach[quan][1] = j;
					}
				}
			}
			visDem = new int[quan + 1];

			mapDinh = new int[quan + 1][quan + 1];

			for (int i = 0; i < quan + 1; i++) {
				bfs(danhSach[i][0], danhSach[i][1], i);
				resetVis();
			}
			backTrack(0, 0, 0);

			System.out.println("Case #" + tc);
			System.out.println(ans);

			// for (int i = 0; i < quan+1; i++) {
			// for (int j = 0; j < quan+1; j++) {
			// System.out.print(mapDinh[i][j]+" ");
			// }
			// System.out.println();
			// }

		}

	}

	static void backTrack(int a, int sum, int k) {
		if (sum > ans) {
			return;
		}
		if (k == quan) {
			if (sum < ans) {
				ans = sum;
			}
			return;
		}

		for (int i = 1; i < quan + 1; i++) {
			if (visDem[i] == 0) {
				visDem[i] = 1;
				backTrack(i, sum + mapDinh[a][i], k + 1);
				visDem[i] = 0;
			}

		}

	}

	static void bfs(int a, int b, int k) {
		myQx.enQueue(a);
		myQy.enQueue(b);
		myQd.enQueue(0);
		vis[a][b] = 1;
		// if (map[a][b] == 1) {
		// visDem[a][b] = 1;
		// }
		while (!myQx.isEmpty()) {
			int x = myQx.deQueue();
			int y = myQy.deQueue();
			int d = myQd.deQueue();
			for (int i = 0; i < 8; i++) {
				int r = x + dx[i];
				int c = y + dy[i];
				if (r >= 0 && c >= 0 && r < N && c < M) {
					if (map[r][c] == 0 && vis[r][c] == 0) {
						myQx.enQueue(r);
						myQy.enQueue(c);
						myQd.enQueue(d + 1);
						vis[r][c] = 1;
					}
					if (map[r][c] == 1 && vis[r][c] == 0) {
						myQx.enQueue(r);
						myQy.enQueue(c);
						myQd.enQueue(d + 1);
						vis[r][c] = 1;
						int z = 0;
						for (int j = 0; j < quan + 1; j++) {
							if (danhSach[j][0] == r && danhSach[j][1] == c) {
								z = j;
							}
						}
						mapDinh[k][z] = d + 1;
					}
				}
			}
		}

	}

	static void resetVis() {
		vis = new int[N][M];
		myQx.resetQ();
		myQy.resetQ();
		myQd.resetQ();
	}
}

class MyQueue {
	private int front, rear, maxQueue;
	private int[] map;

	public MyQueue(int s) {
		maxQueue = s;
		map = new int[maxQueue];
		front = rear = -1;
	}

	public boolean isEmpty() {
		if (front == rear) {
			return true;
		}

		return false;
	}

	public boolean isFull() {
		if (front == rear) {
			return true;
		}

		return false;
	}

	public void resetQ() {
		front = rear = -1;
	}

	public void enQueue(int inValue) {
		rear++;
		map[rear] = inValue;
	}

	public int deQueue() {
		front++;
		return map[front];
	}
}
























//Hugo Ban Dau





import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Solution {
	static int N, M, Hx, Hy, P, ans;
	static int[][] map;
	static int[][] vis;
	static int[][] visDau;
	static MyQueue myQ1 = new MyQueue(500000);
	static MyQueue myQ2 = new MyQueue(500000);
	static MyQueue myQ3 = new MyQueue(500000);
	static int[] dx = { -1, 0, 1, 0 };
	static int[] dy = { 0, 1, 0, -1 };
	static int[][] ong = { { 1, 2, 5, 6 }, { 1, 3, 6, 7 }, { 1, 2, 4, 7 },
			{ 1, 3, 4, 5 } };

	public static void main(String[] args) {
		long startTime = System.currentTimeMillis();
		try {
			System.setIn(new FileInputStream("input.txt"));
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}

		Scanner sc = new Scanner(System.in);

		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			ans = 0;

			N = sc.nextInt();
			M = sc.nextInt();
			Hx = sc.nextInt();
			Hy = sc.nextInt();
			P = sc.nextInt();
			map = new int[N][M];
			vis = new int[N][M];
			visDau = new int[N][M];
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					map[i][j] = sc.nextInt();
					vis[i][j] = 0;
				}
			}

			myQ1.enQueue(Hx);
			myQ2.enQueue(Hy);
			myQ3.enQueue(1);
			vis[Hx][Hy] = 1;
			bfs();
			myQ1.resetQ();
			myQ2.resetQ();
			myQ3.resetQ();
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if (visDau[i][j] == 1) {
						ans++;
					}
				}
			}
			System.out.println("Case #" + tc);
			System.out.println(ans + 1);

		}
		
		long endTime = System.currentTimeMillis();
		long totalTime = endTime - startTime;
		System.out.println("Total time: " + totalTime + " milliseconds");
	}

	static void bfs() {

		while (!myQ1.isEmpty()) {
			int x = myQ1.deQueue();
			int y = myQ2.deQueue();
			int d = myQ3.deQueue();
			for (int i = 0; i < 4; i++) {
				int r = x + dx[i];
				int c = y + dy[i];
				if (r >= 0 && c >= 0 && r < N && c < M) {
					if (map[x][y] == 1 && vis[r][c] == 0) {
						if (map[r][c] == ong[i][0] || map[r][c] == ong[i][1]
								|| map[r][c] == ong[i][2]
								|| map[r][c] == ong[i][3]) {
							myQ1.enQueue(r);
							myQ2.enQueue(c);
							myQ3.enQueue(d + 1);
							vis[r][c] = 1;
							if (d + 1 <= P) {
								visDau[r][c] = 1;
							}
						}

					}
					if (map[x][y] == 2 && vis[r][c] == 0) {
						if (i == 0 || i == 2) {
							if (map[r][c] == ong[i][0]
									|| map[r][c] == ong[i][1]
									|| map[r][c] == ong[i][2]
									|| map[r][c] == ong[i][3]) {
								myQ1.enQueue(r);
								myQ2.enQueue(c);
								myQ3.enQueue(d + 1);
								vis[r][c] = 1;
								if (d + 1 <= P) {
									visDau[r][c] = 1;
								}
							}

						}

					}
					if (map[x][y] == 3 && vis[r][c] == 0) {
						if (i == 1 || i == 3) {
							if (map[r][c] == ong[i][0]
									|| map[r][c] == ong[i][1]
									|| map[r][c] == ong[i][2]
									|| map[r][c] == ong[i][3]) {
								myQ1.enQueue(r);
								myQ2.enQueue(c);
								myQ3.enQueue(d + 1);
								vis[r][c] = 1;
								if (d + 1 <= P) {
									visDau[r][c] = 1;
								}
							}

						}

					}
					if (map[x][y] == 4 && vis[r][c] == 0) {
						if (i == 0 || i == 1) {
							if (map[r][c] == ong[i][0]
									|| map[r][c] == ong[i][1]
									|| map[r][c] == ong[i][2]
									|| map[r][c] == ong[i][3]) {
								myQ1.enQueue(r);
								myQ2.enQueue(c);
								myQ3.enQueue(d + 1);
								vis[r][c] = 1;
								if (d + 1 <= P) {
									visDau[r][c] = 1;
								}
							}

						}

					}
					if (map[x][y] == 5 && vis[r][c] == 0) {
						if (i == 1 || i == 2) {
							if (map[r][c] == ong[i][0]
									|| map[r][c] == ong[i][1]
									|| map[r][c] == ong[i][2]
									|| map[r][c] == ong[i][3]) {
								myQ1.enQueue(r);
								myQ2.enQueue(c);
								myQ3.enQueue(d + 1);
								vis[r][c] = 1;
								if (d + 1 <= P) {
									visDau[r][c] = 1;
								}
							}

						}

					}
					if (map[x][y] == 6 && vis[r][c] == 0) {
						if (i == 2 || i == 3) {
							if (map[r][c] == ong[i][0]
									|| map[r][c] == ong[i][1]
									|| map[r][c] == ong[i][2]
									|| map[r][c] == ong[i][3]) {
								myQ1.enQueue(r);
								myQ2.enQueue(c);
								myQ3.enQueue(d + 1);
								vis[r][c] = 1;
								if (d + 1 <= P) {
									visDau[r][c] = 1;
								}
							}

						}
					}
					if (map[x][y] == 7 && vis[r][c] == 0) {
						if (i == 0 || i == 3) {
							if (map[r][c] == ong[i][0]
									|| map[r][c] == ong[i][1]
									|| map[r][c] == ong[i][2]
									|| map[r][c] == ong[i][3]) {
								myQ1.enQueue(r);
								myQ2.enQueue(c);
								myQ3.enQueue(d + 1);
								vis[r][c] = 1;
								if (d + 1 <= P) {
									visDau[r][c] = 1;
								}
							}
						}
					}
				}
			}

		}
	}
}

class MyQueue {
	private int front, rear, maxQueue;
	private int[] Arrayqueue;

	public MyQueue(int s) {
		maxQueue = s;
		Arrayqueue = new int[maxQueue];
		front = rear = -1;
	}

	public boolean isEmpty() {
		if (front == rear) {
			return true;
		}
		return false;
	}

	public boolean isFull() {
		if (front == rear) {
			return true;
		}
		return false;
	}

	public void resetQ() {
		front = rear = -1;
	}

	public void enQueue(int invalue) {
		rear++;
		Arrayqueue[rear] = invalue;
	}

	public int deQueue() {
		front++;
		return Arrayqueue[front];
	}

}





















//Quang Cao



import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Solution {
	static int N, L1, L2, L3, P1, P2, P3, ans;
	static int[][] danhSach;
	static int[] ads;
	static int[] diem;
	static int[][] timeAds;

	public static void main(String[] args) {

		try {
			System.setIn(new FileInputStream("input1.txt"));
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}

		Scanner sc = new Scanner(System.in);

		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			ans = 0;

			N = sc.nextInt();

			ads = new int[3];
			diem = new int[3];
			danhSach = new int[N][3];
			timeAds = new int[3][2];

			ads[0] = sc.nextInt();
			ads[1] = sc.nextInt();
			ads[2] = sc.nextInt();
			diem[0] = sc.nextInt();
			diem[1] = sc.nextInt();
			diem[2] = sc.nextInt();

			int max = 0;
			int min = 500;
			for (int i = 0; i < N; i++) {
				danhSach[i][0] = sc.nextInt();
				danhSach[i][1] = sc.nextInt();
				danhSach[i][2] = danhSach[i][0] + danhSach[i][1];
				if (max < danhSach[i][2]) {
					max = danhSach[i][2];
				}
			}

			backTrack(0, max);

			System.out.println("Case #" + tc);
			System.out.println(ans);

		}

	}

	static void backTrack(int k, int max) {
		if (k == 3) {
			if (set() > ans) {
				ans = set();
			}
			return;
		}
		for (int i = 1; i <= max; i++) {
			if (check(i, k)) {
				timeAds[k][0] = i;
				timeAds[k][1] = i + ads[k];
				backTrack(k + 1, max);
				timeAds[k][0] = 0;
				timeAds[k][1] = 0;
			}

		}

	}

	private static int set() {
		int rs = 0;
		for (int i = 0; i < N; i++) {
			int sum = 0;
			for (int j = 0; j < 3; j++) {
				int temp = 0;
				if (danhSach[i][0] <= timeAds[j][0]
						&& danhSach[i][2] >= timeAds[j][1]) {
					temp = diem[j];
					if (sum < temp) {
						sum = temp;
					}
				}
			}
			rs += sum;
		}
		return rs;

	}

	static boolean check(int timeStart, int k) {
		int timeEnd = timeStart + ads[k];
		for (int i = 0; i < 3; i++) {
			if (i != k && timeAds[i][0] != 0) {
				if (timeStart > timeAds[i][0] && timeStart < timeAds[i][1]) {
					return false;
				}
				if (timeStart <= timeAds[i][0] && timeEnd >= timeAds[i][1]) {
					return false;
				}
				if (timeEnd > timeAds[i][0] && timeEnd < timeAds[i][1]) {
					return false;
				}
			}
		}

		return true;

	}
}





































// Domino






import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Solution {
	static int N, M, ans;
	static int[][] map;
	static int[][] vis;
	static int[][] arr;
	static int[] dx = { 0, 1 };
	static int[] dy = { 1, 0 };

	public static void main(String[] args) {

		try {
			System.setIn(new FileInputStream("input1.txt"));
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}

		Scanner sc = new Scanner(System.in);

		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			ans = 0;
			map = new int[7][8];
			vis = new int[7][8];
			arr = new int[28][2];
			for (int i = 0; i < 7; i++) {
				for (int j = 0; j < 8; j++) {
					map[i][j] = sc.nextInt();
				}
			}
			for (int i = 0; i < 28; i++) {
				arr[i][0] = -1;
				arr[i][1] = -1;
			}

			backTrack(0);

			System.out.println("Case #" + tc);
			System.out.println(ans);

		}

	}

	static void backTrack(int quanCo) {
		if (quanCo == 28) {
			ans++;
			return;
		}
		for (int i = 0; i < 7; i++) {
			for (int j = 0; j < 8; j++) {
				if (vis[i][j] == 0) {
					vis[i][j] = 1;
					arr[quanCo][0] = map[i][j];
					for (int k = 0; k < 2; k++) {
						int x = i + dx[k];
						int y = j + dy[k];
						if (x >= 0 && y >= 0 && x < 7 && y < 8) {
							if (vis[x][y] == 0) {
								arr[quanCo][1] = map[x][y];
								if (check(arr[quanCo][0], arr[quanCo][1])) {
									vis[x][y] = 1;
									backTrack(quanCo + 1);
									arr[quanCo][1] = -1;
									vis[x][y] = 0;
								}

							}
						}
					}
					arr[quanCo][0] = -1;
					vis[i][j] = 0;
					return;
				}

			}
		}
	}

	static boolean check(int arrX, int arrY) {
		int count = 0;
		for (int i = 0; i < 28; i++) {
			if ((arrX == arr[i][0] && arrY == arr[i][1])
					|| (arrX == arr[i][1] && arrY == arr[i][0])) {
				count++;
			}

		}
		if (count == 2) {
			return false;
		} else {
			return true;
		}

	}
}






//TestCase

50
6 4 6 0 6 3 1 2 
6 1 5 3 5 0 4 0 
2 4 1 5 0 2 4 4 
5 5 1 3 6 5 4 1 
0 3 3 4 4 5 5 2 
2 3 2 6 1 1 0 1 
3 3 0 0 2 2 6 6 

3 3 3 2 6 6 4 6 
2 1 0 1 5 0 6 1 
4 1 4 3 0 4 0 2 
0 0 6 0 2 2 0 3 
3 1 5 2 2 4 3 5 
2 6 5 5 1 5 3 6 
5 4 4 4 6 5 1 1 

2 3 6 6 2 1 6 4 
1 3 2 2 5 4 3 4 
5 2 1 0 0 0 0 5 
4 4 1 1 5 3 6 3 
2 0 4 1 0 3 0 4 
2 6 6 1 0 6 2 4 
5 5 5 1 6 5 3 3 

0 0 1 3 2 6 0 6 
1 2 0 1 5 4 2 0 
0 4 1 4 4 6 1 6 
0 5 3 6 2 3 4 4 
5 6 5 5 5 2 0 3 
2 2 6 6 2 4 5 1 
3 4 1 1 3 3 5 3 

5 3 1 6 0 5 3 0 
4 2 1 4 4 3 6 2 
3 2 2 5 6 5 2 1 
2 0 1 0 1 1 3 6 
5 5 1 5 6 4 2 2 
0 4 4 5 6 6 6 0 
0 0 3 3 1 3 4 4 

2 0 1 5 0 5 5 4 
3 1 2 4 6 4 1 1 
1 2 3 6 5 2 3 0 
4 1 3 4 0 4 6 1 
6 6 3 2 0 6 5 6 
1 0 6 2 2 2 0 0 
5 3 5 5 4 4 3 3 

5 2 0 3 1 4 6 3 
5 1 3 2 6 0 0 4 
5 3 5 6 6 6 5 4 
6 4 4 4 1 0 1 1 
3 4 1 3 1 2 2 4 
2 2 6 1 2 0 5 0 
2 6 5 5 0 0 3 3 

5 6 2 5 2 6 4 3 
1 3 0 0 6 1 6 0 
3 5 5 4 0 2 1 5 
0 4 6 6 1 1 0 3 
6 4 3 2 0 1 1 2 
3 3 4 2 4 1 2 2 
0 5 5 5 4 4 3 6 

5 5 0 3 4 2 4 1 
1 5 2 0 6 5 5 0 
6 0 1 1 5 2 6 3 
4 6 3 2 2 2 6 6 
0 1 3 1 3 4 2 6 
0 4 3 3 5 4 1 2 
1 6 5 3 0 0 4 4 

6 2 5 2 5 5 4 1 
5 3 5 0 6 4 2 2 
3 6 1 6 1 2 0 2 
0 6 3 2 2 4 1 0 
4 5 4 3 6 6 5 1 
3 0 4 4 5 6 3 1 
3 3 0 4 1 1 0 0 

4 6 6 0 0 1 6 6 
0 0 2 4 0 3 5 6 
1 6 2 5 3 2 5 4 
4 0 1 4 3 4 2 0 
4 4 5 1 5 5 1 1 
3 6 0 5 2 1 2 2 
2 6 1 3 3 5 3 3 

3 1 0 3 1 5 1 1 
4 1 5 4 5 2 5 6 
6 0 0 2 3 2 4 3 
3 6 2 2 0 5 4 2 
5 5 1 0 0 4 3 5 
6 1 2 6 3 3 6 6 
2 1 4 6 0 0 4 4 

3 0 0 1 4 5 6 2 
6 3 2 0 2 2 1 1 
4 6 4 2 2 3 0 0 
5 2 1 4 5 0 1 3 
5 5 5 3 5 1 4 0 
6 0 5 6 4 4 2 1 
1 6 4 3 3 3 6 6 

2 4 4 5 0 4 0 3 
0 0 4 3 2 0 5 6 
3 6 3 2 6 6 2 6 
3 5 2 5 1 6 0 1 
4 4 2 1 0 6 6 4 
5 0 5 5 3 1 2 2 
4 1 1 5 1 1 3 3 

1 5 4 0 0 1 5 4 
1 4 2 2 5 3 6 1 
4 3 1 1 0 6 3 2 
4 4 1 3 0 2 2 4 
3 3 4 6 3 6 2 5 
5 6 0 0 2 1 6 6 
6 2 0 5 3 0 5 5 

4 6 5 2 0 2 0 0 
5 3 6 1 2 3 6 5 
5 1 1 2 2 4 6 3 
0 4 1 0 6 6 5 4 
1 4 6 0 3 3 6 2 
1 3 3 0 5 0 4 3 
5 5 1 1 2 2 4 4 

3 6 2 4 1 6 3 3 
4 0 1 5 2 2 4 1 
5 6 0 0 6 4 1 0 
1 3 5 3 6 6 2 0 
4 3 0 5 0 6 1 1 
5 2 2 6 1 2 2 3 
5 4 5 5 3 0 4 4 

5 6 3 6 6 0 4 0 
6 4 1 1 4 3 4 5 
3 3 2 0 1 2 2 4 
6 2 2 2 5 0 5 2 
3 1 2 3 3 5 4 4 
5 1 4 1 0 1 6 1 
0 3 5 5 0 0 6 6 

3 5 2 2 3 0 6 2 
0 4 5 1 3 2 3 1 
6 0 4 6 0 1 3 3 
6 1 0 0 1 1 5 4 
4 1 3 6 5 0 3 4 
5 6 1 2 0 2 4 4 
2 5 5 5 2 4 6 6 

2 5 3 1 0 5 0 3 
6 3 5 5 6 0 0 1 
4 1 3 5 4 4 2 1 
4 2 1 6 6 2 4 0 
2 2 1 5 3 4 2 0 
5 4 6 4 3 2 6 5 
1 1 0 0 3 3 6 6 

4 6 2 0 5 5 6 0 
5 6 5 2 0 0 4 3 
3 1 2 1 5 1 4 1 
3 5 0 3 2 2 6 3 
2 6 4 4 5 0 2 3 
2 4 1 1 1 0 6 6 
5 4 1 6 4 0 3 3 

1 1 0 4 5 1 3 5 
1 0 0 5 6 1 0 3 
5 2 4 4 4 6 0 2 
3 1 3 6 4 5 6 6 
6 2 3 2 3 3 2 2 
0 0 2 1 4 2 6 0 
3 4 5 6 1 4 5 5 

6 5 2 0 0 5 5 3 
6 2 1 2 1 6 4 0 
5 1 5 2 4 3 4 4 
1 4 2 2 6 3 4 5 
2 4 6 0 3 1 6 6 
3 0 6 4 1 1 1 0 
3 2 5 5 3 3 0 0 

6 2 1 5 0 6 6 4 
5 2 0 0 2 0 1 6 
4 4 4 5 0 5 0 1 
3 6 5 3 2 1 3 0 
3 2 2 2 4 2 3 1 
5 5 1 1 4 1 5 6 
4 0 4 3 6 6 3 3 

0 3 1 2 3 5 0 4 
5 4 3 2 6 1 1 0 
2 6 4 3 4 1 3 3 
3 1 5 0 6 6 0 6 
4 6 6 3 0 2 1 1 
2 2 5 2 0 0 5 6 
1 5 4 2 4 4 5 5 

1 0 5 4 6 3 2 2 
5 1 1 2 4 2 3 2 
3 4 0 6 4 6 3 5 
2 0 6 6 5 0 2 6 
6 5 3 3 2 5 1 6 
0 3 4 0 5 5 1 1 
1 4 0 0 1 3 4 4 

2 0 4 4 1 2 0 0 
2 4 2 2 6 0 6 3 
5 5 4 0 5 4 3 5 
3 3 1 3 1 6 5 2 
0 5 2 3 5 6 0 3 
6 6 2 6 6 4 1 4 
1 0 1 1 1 5 4 3 

6 5 4 0 2 4 3 1 
5 3 1 5 6 3 3 4 
5 4 6 4 3 3 2 5 
5 0 3 0 1 2 2 0 
4 4 1 0 2 6 3 2 
1 6 6 0 1 1 5 5 
0 0 4 1 6 6 2 2 

1 0 3 3 1 2 1 3 
5 5 3 5 5 1 2 4 
0 2 3 4 2 5 1 1 
3 0 6 4 0 0 4 5 
6 5 6 6 6 3 6 1 
3 2 6 2 0 5 0 6 
0 4 4 4 2 2 4 1 

4 0 6 3 6 1 0 3 
4 1 2 0 0 6 2 2 
5 2 1 5 6 5 5 5 
2 3 1 3 6 6 0 5 
3 4 2 1 6 4 4 5 
6 2 1 0 4 2 5 3 
3 3 0 0 4 4 1 1 

0 2 4 4 2 1 3 6 
3 5 6 6 1 3 4 1 
6 5 2 6 3 0 4 0 
1 5 2 3 6 1 2 2 
5 0 0 1 0 6 4 3 
4 2 1 1 2 5 6 4 
4 5 0 0 3 3 5 5 

2 3 0 4 6 6 2 6 
2 1 5 2 1 6 3 0 
0 5 0 6 5 6 5 4 
2 2 3 3 6 3 4 1 
6 4 1 0 0 0 5 5 
4 4 1 1 1 5 3 4 
3 1 0 2 2 4 5 3 

4 0 3 3 2 2 6 5 
3 0 4 6 4 3 0 2 
4 1 0 5 4 5 5 5 
6 6 0 6 3 6 3 1 
4 4 0 1 6 2 2 5 
3 5 1 2 1 1 2 4 
3 2 0 0 5 1 6 1 

6 1 2 3 6 0 6 4 
4 4 3 0 5 3 1 5 
1 2 3 1 6 2 1 1 
3 4 5 0 4 0 2 4 
6 3 5 6 5 4 0 2 
1 0 5 5 5 2 4 1 
6 6 3 3 2 2 0 0 

2 1 6 1 0 5 5 1 
4 0 0 3 4 2 6 3 
1 3 2 6 1 4 3 5 
1 0 0 0 5 2 4 3 
0 6 4 5 2 2 3 2 
2 0 6 4 5 6 6 6 
4 4 3 3 1 1 5 5 

1 0 0 5 1 2 3 1 
6 4 2 6 0 4 2 0 
3 3 4 2 4 5 3 2 
5 6 0 0 5 2 0 3 
6 0 3 5 3 6 4 1 
2 2 1 6 3 4 6 6 
5 5 4 4 1 5 1 1 

1 5 3 5 1 6 2 4 
4 4 4 3 0 0 0 4 
2 1 6 2 4 5 3 6 
2 3 0 2 0 5 0 6 
6 5 1 4 2 5 3 0 
1 1 2 2 1 3 4 6 
5 5 0 1 6 6 3 3 

0 1 5 5 6 0 2 4 
1 5 0 2 4 3 6 5 
5 3 4 0 1 3 6 1 
6 6 0 5 4 4 4 1 
0 3 1 1 2 6 0 0 
2 1 4 5 3 3 2 2 
3 6 2 3 6 4 2 5 

1 4 2 6 1 6 4 6 
6 5 3 4 0 3 0 2 
5 2 2 4 0 0 6 3 
5 0 4 4 1 1 6 0 
4 5 5 1 3 1 5 5 
3 5 1 0 1 2 2 2 
3 2 4 0 3 3 6 6 

1 6 0 6 4 0 0 2 
1 3 3 3 4 3 1 2 
5 5 0 3 3 2 4 5 
3 6 5 6 0 5 4 4 
1 4 5 1 1 0 0 0 
1 1 2 6 4 2 6 6 
5 3 2 5 4 6 2 2 

3 5 1 4 6 3 2 0 
2 3 0 5 1 3 4 0 
6 4 2 1 2 4 2 2 
1 0 0 0 4 3 5 6 
4 4 3 0 1 1 5 1 
5 2 5 5 6 2 0 6 
3 3 1 6 4 5 6 6 

6 0 0 5 6 1 5 2 
2 1 3 2 6 6 6 5 
4 1 4 0 1 0 5 4 
3 4 0 3 4 2 6 4 
2 2 2 0 6 3 3 5 
3 3 5 1 1 1 2 6 
1 3 4 4 5 5 0 0 

6 0 3 0 2 4 0 2 
1 5 3 3 4 4 5 3 
3 6 4 5 3 1 4 6 
6 5 2 5 1 0 5 0 
2 3 1 1 1 2 1 6 
2 2 6 2 1 4 0 0 
4 3 5 5 0 4 6 6 

0 3 6 5 3 2 5 3 
4 2 1 6 6 4 3 4 
1 0 1 4 5 4 0 5 
0 2 0 6 3 6 2 5 
6 6 1 3 2 2 1 5 
6 2 4 0 4 4 1 1 
3 3 0 0 1 2 5 5 

5 0 3 1 4 0 0 1 
2 0 2 2 6 1 2 6 
0 3 2 1 3 3 4 6 
1 5 3 5 3 4 0 6 
1 1 4 1 0 0 5 6 
2 5 4 2 5 4 6 6 
4 4 6 3 5 5 3 2 

0 5 6 4 1 0 0 0 
2 5 6 2 5 6 3 5 
4 3 4 2 3 6 0 4 
1 5 1 2 5 5 6 1 
1 3 1 1 2 3 3 3 
4 4 6 0 4 1 2 2 
6 6 2 0 4 5 0 3 

5 0 3 2 1 3 3 0 
6 5 5 4 3 6 1 4 
4 0 1 0 5 1 2 4 
0 2 5 5 0 0 5 3 
3 4 6 2 4 6 1 2 
3 3 6 6 0 6 2 5 
4 4 1 1 6 1 2 2 

4 1 4 0 5 6 6 4 
3 5 0 3 5 1 0 2 
6 1 4 5 0 6 3 1 
5 5 4 3 3 3 3 2 
2 6 5 0 2 1 1 1 
0 1 4 4 4 2 5 2 
6 6 3 6 2 2 0 0 

3 5 4 4 2 1 1 6 
1 4 4 0 3 4 4 5 
0 6 0 2 5 1 0 5 
3 6 2 5 5 5 2 6 
3 1 0 1 5 6 0 0 
3 2 2 2 0 3 6 4 
2 4 6 6 3 3 1 1 

2 4 4 5 1 2 6 3 
1 0 4 1 4 4 5 5 
2 2 6 1 0 0 5 0 
4 0 0 3 5 6 2 5 
6 4 1 3 1 5 3 3 
0 6 5 3 0 2 6 2 
3 2 3 4 1 1 6 6





































//Chi ong Nau nau Nau Nau Nau












import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Solution {
	static int M, N, ans, max, min, mid;
	static int[][] map;
	static int[] dxC = { 0, 1, 0, -1, -1, -1 };
	static int[] dyC = { 1, 0, -1, -1, 0, 1 };
	static int[] dxL = { 0, 1, 1, 1, 0, -1 };
	static int[] dyL = { 1, 1, 0, -1, -1, 0 };
	static int[][] vis;

	public static void main(String[] args) {

		try {
			System.setIn(new FileInputStream("input1.txt"));
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}

		Scanner sc = new Scanner(System.in);

		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			ans = 0;

			N = sc.nextInt();
			M = sc.nextInt();
			map = new int[M][N];
			vis = new int[M][N];
			//min = 2000;
			//max = 0;
			for (int i = 0; i < M; i++) {
				for (int j = 0; j < N; j++) {
					map[i][j] = sc.nextInt();
//					if (map[i][j] < min) {
//						min = map[i][j];
//					}
//					if (map[i][j] > max) {
//						max = map[i][j];
//					}
				}
			}

			// mid = (max + min) / 2;
			for (int i = 0; i < M; i++) {
				for (int j = 0; j < N; j++) {
					// if (map[i][j] > mid) {
					vis[i][j] = 1;
					backTrack(i, j, map[i][j], 1);
					backTrack1(i, j, map[i][j], 1);
					// if (j % 2 == 0) {
					// backTrack1(i, j, map[i][j], 1);
					// } else {
					// backTrack2(i, j, map[i][j], 1);
					// }

					vis[i][j] = 0;
					// }
				}
			}

			System.out.println("Case #" + tc);
			System.out.println(ans * ans);
		}

	}


	// static void backTrack1(int a, int b, int sum, int k) {
	//
	// if (k == 4) {
	// if (sum > ans) {
	// ans = sum;
	// }
	// return;
	// }
	// for (int i = 0; i < 6; i++) {
	// int x = a + dxC[i];
	// int y = b + dyC[i];
	// if (x >= 0 && y >= 0 && x < M && y < N && vis[x][y] != 1) {
	// vis[x][y] = 1;
	// backTrack1(a, b, sum + map[x][y], k + 1);
	// vis[x][y] = 0;
	// }
	// }
	//
	// }
	//
	// static void backTrack2(int a, int b, int sum, int k) {
	//
	// if (k == 4) {
	// if (sum > ans) {
	// ans = sum;
	// }
	// return;
	// }
	// for (int i = 0; i < 6; i++) {
	// int x = a + dxL[i];
	// int y = b + dyL[i];
	// if (x >= 0 && y >= 0 && x < M && y < N && vis[x][y] != 1) {
	// vis[x][y] = 1;
	// backTrack2(a, b, sum + map[x][y], k + 1);
	// vis[x][y] = 0;
	// }
	// }
	//
	// }

	static void backTrack(int a, int b, int sum, int k) {
		if (k == 4) {
			if (sum > ans) {
				ans = sum;
			}
			return;
		}
		for (int i = 0; i < 6; i++) {
			if (b % 2 == 0) {
				int x = a + dxC[i];
				int y = b + dyC[i];
				if (x >= 0 && y >= 0 && x < M && y < N && vis[x][y] != 1) {
					vis[x][y] = 1;
					backTrack(x, y, sum + map[x][y], k + 1);
					vis[x][y] = 0;
				}
			}
			if (b % 2 != 0) {
				int x = a + dxL[i];
				int y = b + dyL[i];
				if (x >= 0 && y >= 0 && x < M && y < N && vis[x][y] != 1) {
					vis[x][y] = 1;
					backTrack(x, y, sum + map[x][y], k + 1);
					vis[x][y] = 0;
				}
			}
		}
	}

	static void backTrack1(int a, int b, int sum, int k) {
		if (k == 4) {
			if (sum > ans) {
				ans = sum;
			}
			return;
		}
		for (int i = 0; i < 6; i++) {
			if (b % 2 == 0) {
				int x = a + dxC[i];
				int y = b + dyC[i];
				if (x >= 0 && y >= 0 && x < M && y < N && vis[x][y] != 1) {
					vis[x][y] = 1;
					backTrack1(a, b, sum + map[x][y], k + 1);
					vis[x][y] = 0;
				}
			}
			if (b % 2 != 0) {
				int x = a + dxL[i];
				int y = b + dyL[i];
				if (x >= 0 && y >= 0 && x < M && y < N && vis[x][y] != 1) {
					vis[x][y] = 1;
					backTrack1(a, b, sum + map[x][y], k + 1);
					vis[x][y] = 0;
				}
			}
		}
	}
}






































//Hugo Ve Nha

Hugo đang trền đường về nhà và cần đi qua 1 đoạn đường B.
Trên đoạn đường đi qua có N cổng. Tại mỗi cổng có 1 số lượng binh sĩ và giá để đi qua cổng đó. Muốn đi qua mỗi cổng Hugo có 3 cách lựa chọn.
1. Pass
Trả số tiền quy định ở cổng đó để được đi qua
2. Hire
Trả gấp đôi số tiền ở cổng đó để thuê số binh sĩ gộp vào đoàn quân của mình
3. battle
Điều kiện để đánh nhau là số quân của Hugo >= số lượng lính tại cổng đó. Có các lưu ý:
+ Hugo k được tính vào số lượng của quân
+ Mỗi người lính chỉ tham gia được vào tối đa 3 trận đánh. Sau 3 trận đánh nếu đi nhóm binh sĩ đó còn sống thì cũng giải tán.
+ Mỗi trận đánh thì tất cả số binh sĩ đều tham gia.
+ Đánh nhau chết theo tỉ lệ 1: 1. Ai tham gia trước sẽ bị chết trước
Input:
Dòng đầu tiên là số lượng trường hợp thử nghiệm
Mỗi trường hợp thử nghiệm sẽ có
          Dòng đầu tiên chứa số lượng cổng N
          N dòng tiếp theo chứa 2 số là số binh lính và chi phí tại mỗi cổng
Output: In ra chi phí nhỏ nhất Hugo có thể đi qua đoạn đường B
Điều kiện input: số cổng <=20
-      2 <=Số lính và chi phí đi qua <=1000
VD:
Input
2
7
10 100
70 5
80 15
20 60
50 90
30 80
10 10
9
600 800
300 400
300 400
1000 400
300 600
100 300
600 300
600 500
1000 300
 
Output:
#1 150
#2 3000
Giải thích
 	1	2	3	4	5	6	7
Số binh sĩ	10	70	80	20	50	30	10
Chi phí	100	5	15	60	90	80	10
 
 
 
 
Có thể tính chi phí đi nhỏ nhất
 	1	2	3	4	5	6	7
Số binh sĩ	10	70	80	20	50	30	10
Chi phí	100	5	15	60	90	80	10
Chọn	Pass	Hire	Hire	Battle	Battle	Battle	Pass
Chi phí	100	110	140	 	 	 	150
 




























import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Solution {
	static int N, ans;
	static int[][] map;
	static int[][] vis;
	static int L1, L2, L3;

	public static void main(String[] args) {

		try {
			System.setIn(new FileInputStream("input.txt"));
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}

		Scanner sc = new Scanner(System.in);

		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			ans = 99999999;

			N = sc.nextInt();

			map = new int[N][2];
			L1 = 0;
			L2 = 0;
			L3 = 0;
			for (int i = 0; i < N; i++) {
				map[i][0] = sc.nextInt();
				map[i][1] = sc.nextInt();
			}
			backTrack(0, 0, 0);
			System.out.println("Case #" + tc);
			System.out.println(ans);

		}

	}

	static void backTrack(int k, int sum, int linh) {
		if (ans < sum) {
			return;
		}
		if (k == N) {
			if (ans > sum) {
				ans = sum;
			}
			return;
		}

		for (int i = 0; i < 3; i++) {
			if (i == 0) {
				backTrack(k + 1, sum + map[k][1], linh);
			}
			if (i == 1) {
				L1 += map[k][0];
				backTrack(k + 1, sum + (map[k][1] * 2), linh + L1);
				L1 -= map[k][0];
			}
			if (i == 2) {
				if (linh >= map[k][0]) {
					if (map[k][0] <= L3) {
						int linhDanhXong = L3;
						L3 = L2;
						L2 = L1;
						L1 = 0;
						backTrack(k + 1, sum, linh - linhDanhXong);
						L1 = L2;
						L2 = L3;
						L3 = linhDanhXong;
					} else {
						int conLai = map[k][0] - L3;
						if (conLai <= L2) {
							int linh3DanhXong = L3;
							L3 = L2 - conLai;
							L2 = L1;
							L1 = 0;
							backTrack(k + 1, sum, linh - map[k][0]);
							L1 = L2;
							L2 = L3 + conLai;
							L3 = linh3DanhXong;
						} else {
							int conLaiCuoi = conLai - L2;
							if (conLaiCuoi <= L1) {
								int linh3DanhXong = L3;
								int linh2DanhXong = L2;
								L3 = 0;
								L2 = L1 - conLaiCuoi;
								L1 = 0;
								backTrack(k + 1, sum, linh - map[k][0]);
								L1 = L2 + conLaiCuoi;
								L2 = linh2DanhXong;
								L3 = linh3DanhXong;
							} else {
								return;
							}

						}

					}

				}
			}

		}
	}
}























//Quan Tuong

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Solution {
	static int n, m, q, p, s, t, ans;
	static int[][] map;
	static int[] dx = { -1, 1, 1, -1 };
	static int[] dy = { 1, 1, -1, -1 };
	static MyQueue myQx = new MyQueue(500000);
	static MyQueue myQy = new MyQueue(500000);

	public static void main(String[] args) {

		try {
			System.setIn(new FileInputStream("input.txt"));
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}

		Scanner sc = new Scanner(System.in);

		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			ans = 0;

			n = sc.nextInt();
			m = sc.nextInt();
			p = sc.nextInt();
			q = sc.nextInt();
			s = sc.nextInt();
			t = sc.nextInt();
			map = new int[n + 1][n + 1];

			myQx.resetQ();
			myQy.resetQ();
			for (int i = 1; i <= n; i++) {
				for (int j = 1; j <= n; j++) {
					map[i][j] = -1;
				}
			}

			// map[s][t] = -1;
			for (int i = 1; i <= m; i++) {
				int a = sc.nextInt();
				int b = sc.nextInt();
				map[a][b] = -2;
			}
			bfs();

			// System.out.println("Case #" + tc);
			System.out.println(map[s][t]);
//			for (int i = 1; i <= n; i++) {
//				for (int j = 1; j <= n; j++) {
//					System.out.print(map[i][j] + " ");
//				}
//				System.out.println();
//			}
		}

	}

	static void bfs() {
		myQx.enQueue(p);
		myQy.enQueue(q);
		map[p][q] = 0;
		while (!myQx.isEmpty()) {

			int x = myQx.deQueue();
			int y = myQy.deQueue();

			for (int i = 0; i < 4; i++) {
				int r = x;
				int c = y;
				while (true) {
					r += dx[i];
					c += dy[i];
					if (r < 1 || c < 1 || r > n || c > n || map[r][c] == -2) {
						break;
					}

					else if (map[r][c] == -1 || map[r][c] > map[x][y]) {
						map[r][c] = map[x][y] + 1;
						myQx.enQueue(r);
						myQy.enQueue(c);
					}

				}
			}

		}
	}
}

// int r1 = r + dx[i];
// int c1 = c + dy[i];
// while(r1 >= 0 && c1 >= 0 && r1 < n && c1 < n && map[r1][c1]!=
// -2){
// vis[r1][c1] = vis[r][c] + 1;
// if(r1 == s && c1 == t){
// ans = vis[r][c];
// return;
// }
// myQx.enQueue(r);
// myQy.enQueue(c);
// r1 += dx[i];
// c1 += dy[i];
// }
class MyQueue {
	private int front, rear, maxQueue;
	private int[] map;

	public MyQueue(int s) {
		maxQueue = s;
		map = new int[maxQueue];
		front = rear = -1;
	}

	public boolean isEmpty() {
		if (front == rear) {
			return true;
		}

		return false;
	}

	public boolean isFull() {
		if (front == rear) {
			return true;
		}

		return false;
	}

	public void resetQ() {
		front = rear = -1;
	}

	public void enQueue(int inValue) {
		rear++;
		map[rear] = inValue;
	}

	public int deQueue() {
		front++;
		return map[front];
	}
}
































//Battle City




































































































//