Untitled

package APS2;

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

public class Hugo_DaoVang2 {
	static int N, G, Answer;
	static int[][] map;
	static int[] goldX;
	static int[] goldY;
	static int[][] visit;
	static int[] dx = { 0, 0, -1, 1 };
	static int[] dy = { -1, 1, 0, 0 };

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\APS2\\Hugo_DaoVang2_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			N = sc.nextInt();
			G = sc.nextInt();
			map = new int[N][N];
			goldX = new int[N];
			goldY = new int[N];
			for (int i = 0; i < G; i++) {
				goldX[i] = sc.nextInt() - 1;
				goldY[i] = sc.nextInt() - 1;
			}
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					map[i][j] = sc.nextInt();
				}
			}
			// danh dau nhung vi tri co vang
			// for (int i = 0; i < G; i++) {
			// map[goldX[i]][goldY[i]] = 2;
			// }
			Answer = -1;
			// BFS tung o trong map - cac o so 1 va chua duoc visit
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (map[i][j] == 1) {
						visit = new int[N][N];
						BFS(i, j);
					}
				}
			}

			System.out.println("Case #" + tc);
			if (Answer == -1) {
				System.out.println(-1);
			} else {
				System.out.println(Answer);
			}
		}
	}

	public static void BFS(int i, int j) {
		Queue<Integer> queue = new LinkedList<>();
		queue.add(i);
		queue.add(j);
		visit[i][j] = 1;
		while (!queue.isEmpty()) {
			int curX = queue.poll();
			int curY = queue.poll();
			for (int k = 0; k < 4; k++) {
				int nextX = curX + dx[k];
				int nextY = curY + dy[k];
				if (nextX >= 0 && nextX < N && nextY >= 0 && nextY < N) {
					if (visit[nextX][nextX] == 0 && map[nextX][nextX] != 0) {
						visit[nextX][nextY] = visit[curX][curY] + 1;
					}
				}
			}
		}
		int count = 0;
		int Max = Integer.MIN_VALUE;
		for (int k = 0; k < G; k++) { // xet G vi tri mo vang, xem vi tri co
										// visit lon nhat
			if (visit[goldX[k]][goldY[k]] > 0) {
				count++;
				Max = Math.max(Max, visit[goldX[k]][goldY[k]]);
			}
		}
		if (count == G) {
			if (Answer == -1 || Answer > Max) {
				Answer = Max;
			}
		}
	}
}