# Untitled

unknown
plain_text
a year ago
3.1 kB
2
Indexable
Never
```Dưới đây là một giải pháp cho bài toán Hugo Đào Vàng sử dụng Java và thuật toán BFS:

```java
import java.util.*;

public class HugoGoldMining {
static final int MAXN = 20;
static final int[] dx = {0, 0, -1, 1};
static final int[] dy = {-1, 1, 0, 0};
static int[][] map = new int[MAXN][MAXN];
static int[][] dist = new int[MAXN][MAXN];
static boolean[][] visited = new boolean[MAXN][MAXN];
static int N;
static int G;
static int[] goldX = new int[4];
static int[] goldY = new int[4];

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for (int t = 1; t <= T; t++) {
N = sc.nextInt();
G = sc.nextInt();
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();
}
}
System.out.println("Case #" + t);
System.out.println(solve());
}
}

public static int solve() {
int minDist = Integer.MAX_VALUE;
for (int x = 0; x < N; x++) {
for (int y = 0; y < N; y++) {
if (map[x][y] == 0) continue;
boolean canReachAllGoldMines = true;
for (int i = 0; i < G; i++) {
if (goldX[i] == x && goldY[i] == y) continue;
bfs(x, y);
if (dist[goldX[i]][goldY[i]] == Integer.MAX_VALUE) {
canReachAllGoldMines = false;
break;
}
}
if (!canReachAllGoldMines) continue;
int maxDistToGoldMine = Integer.MIN_VALUE;
for (int i = 0; i < G; i++) {
maxDistToGoldMine = Math.max(maxDistToGoldMine, dist[goldX[i]][goldY[i]]);
}
minDist = Math.min(minDist, maxDistToGoldMine);
}
}
return minDist == Integer.MAX_VALUE ? -1 : minDist;
}

public static void bfs(int startX, int startY) {
for (int i = 0; i < N; i++) {
Arrays.fill(dist[i], Integer.MAX_VALUE);
Arrays.fill(visited[i], false);
}
Queue<Integer> qX = new LinkedList<>();
Queue<Integer> qY = new LinkedList<>();
dist[startX][startY] = 0;
visited[startX][startY] = true;
while (!qX.isEmpty()) {
int x = qX.poll();
int y = qY.poll();
for (int k = 0; k < 4; k++) {
int nx = x + dx[k];
int ny = y + dy[k];
if (nx >= 0 && nx < N && ny >= 0 && ny < N && map[nx][ny] == 1 && !visited[nx][ny]) {
visited[nx][ny] = true;
dist[nx][ny] = dist[x][y] + 1;