# Untitled

unknown
plain_text
20 days ago
2.1 kB
1
Indexable
Never
```
public class Solution {

static PoitnCs[] golds;
static int[][] map;
static int[][] step;
static int minDis;
static Queue<PoitnCs> qt;
static int n;
static int[] dx = { -1, 0, 1, 0 };
static int[] dy = { 0, 1, 0, -1 };

public static void main(String args[]) throws Exception {
Scanner sc = new Scanner(System.in);

int T = sc.nextInt();
qt = new Queue<Solution.PoitnCs>();

for (int tc = 1; tc <= T; tc++) {

n = sc.nextInt();
int g = sc.nextInt();

minDis = 9999;

golds = new PoitnCs[g];
for (int i = 0; i < g; i++) {
golds[i] = new PoitnCs(sc.nextInt(), sc.nextInt());
}

map = new int[n + 1][n + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
map[i][j] = sc.nextInt();
}
}
System.out.println(solve());
}
}

static int solve() throws Exception {
for (int i = 1; i <= map.length - 1; i++) {
for (int j = 1; j <= map.length - 1; j++) {
if (map[i][j] != 0) {
step = new int[map.length][map.length];
bfs(i, j);

boolean canGoAllGolds = true;
for (int k = 0; k < golds.length; k++) {
if (step[golds[k].x][golds[k].y] == 0) {
canGoAllGolds = false;
break;
}
}

if (!canGoAllGolds) {
continue;
}

int maxDistanceToGold = 0;
for (int k = 0; k < golds.length; k++) {
int stepGold = step[golds[k].x][golds[k].y] - 1;
maxDistanceToGold = Math.max(maxDistanceToGold,
stepGold);
}
minDis = Math.min(minDis, maxDistanceToGold);
}
}
}
return (minDis == 9999) ? -1 : minDis;
}

private static void bfs(int x, int y) throws Exception {
qt.reset();
qt.enQueue(new PoitnCs(x, y));
step[x][y] = 1;
PoitnCs tmp;
while (!qt.isEmpty()) {
tmp = qt.peek();
qt.deQueue();

for (int i = 0; i < dx.length; i++) {
int xx = tmp.x + dx[i];
int yy = tmp.y + dy[i];
if (xx < 1 || xx >= map.length || yy < 1 || yy >= map.length
|| map[xx][yy] == 0) {
continue;
}
if (step[xx][yy] == 0) {
step[xx][yy] = step[tmp.x][tmp.y] + 1;
qt.enQueue(new PoitnCs(xx, yy));
}
}
}
}```