Untitled

mail@pastecode.io avatar
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<>();
        qX.add(startX);
        qY.add(startY);
        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;
                    qX.add(nx);
                    qY.add(ny);
                }
            }
        }
    }
}
```