追逐游戏

/*
题目思路：
1. 建立图的表示：使用邻接表来表示无向图。
2. BFS策略：使用广度优先搜索来计算小力从起点到达其他点的最短距离，同时计算小扣从起点到达其他点的最短距离。
3. 最优策略：小力追小扣的过程中，小力每次尽量靠近小扣，而小扣则尽量远离小力。
4. 终止条件：一旦小力与小扣在同一位置则游戏结束，否则若小力无法追上小扣则返回 -1。
*/
import java.util.*;
import java.util.stream.Collectors;

public class ChasingGameStream {
    public int minRoundsToCatch(int[][] edges, int startA, int startB) {
        int n = edges.length;
        Map<Integer, List<Integer>> graph = Arrays.stream(edges).collect(Collectors.groupingBy(
            edge -> edge[0], Collectors.mapping(edge -> edge[1], Collectors.toList())
        ));
        graph.putAll(Arrays.stream(edges).collect(Collectors.groupingBy(
            edge -> edge[1], Collectors.mapping(edge -> edge[0], Collectors.toList())
        )));
        int[] distA = bfs(graph, startA, n);
        int[] distB = bfs(graph, startB, n);
        return IntStream.range(1, n + 1).filter(i -> distA[i] <= distB[i]).findFirst().orElse(-1);
    }

    private int[] bfs(Map<Integer, List<Integer>> graph, int start, int n) {
        int[] dist = new int[n + 1];
        Arrays.fill(dist, -1);
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);
        dist[start] = 0;
        while (!queue.isEmpty()) {
            int node = queue.poll();
            graph.getOrDefault(node, Collections.emptyList()).stream()
                .filter(neighbor -> dist[neighbor] == -1)
                .forEach(neighbor -> {
                    dist[neighbor] = dist[node] + 1;
                    queue.offer(neighbor);
                });
        }
        return dist;
    }
}