追逐游戏

难度: Hard

秋游中的小力和小扣设计了一个追逐游戏。他们选了秋日市集景区中的 N 个景点，景点编号为 1~N。此外，他们还选择了 N 条小路，满足任意两个景点之间都可以通过小路互相到达，且不存在两条连接景点相同的小路。整个游戏场景可视作一个无向连通图，记作二维数组 `edges`，数组中以 `[a,b]` 形式表示景点 a 与景点 b 之间有一条小路连通。小力和小扣只能沿景点间的小路移动。小力的目标是在最快时间内追到小扣，小扣的目标是尽可能延后被小力追到的时间。游戏开始前，两人分别站在两个不同的景点 `startA` 和 `startB`。每一回合，小力先行动，小扣观察到小力的行动后再行动。小力和小扣在每回合可选择以下行动之一： - 移动至相邻景点 - 留在原地如果小力追到小扣（即两人于某一时刻出现在同一位置），则游戏结束。若小力可以追到小扣，请返回最少需要多少回合；若小力无法追到小扣，请返回 -1。注意：小力和小扣一定会采取最优移动策略。 **示例 1：** >输入：`edges = [[1,2],[2,3],[3,4],[4,1],[2,5],[5,6]], startA = 3, startB = 5` > >输出：`3` > >解释： >![image.png](https://pic.leetcode-cn.com/1597991318-goeHHr-image.png){:height="250px"} > >第一回合，小力移动至 2 号点，小扣观察到小力的行动后移动至 6 号点； >第二回合，小力移动至 5 号点，小扣无法移动，留在原地； >第三回合，小力移动至 6 号点，小力追到小扣。返回 3。 **示例 2：** >输入：`edges = [[1,2],[2,3],[3,4],[4,1]], startA = 1, startB = 3` > >输出：`-1` > >解释： >![image.png](https://pic.leetcode-cn.com/1597991157-QfeakF-image.png){:height="250px"} > >小力如果不动，则小扣也不动；否则小扣移动到小力的对角线位置。这样小力无法追到小扣。 **提示：** - `edges` 的长度等于图中节点个数 - `3 <= edges.length <= 10^5` - `1 <= edges[i][0], edges[i][1] <= edges.length 且 edges[i][0] != edges[i][1]` - `1 <= startA, startB <= edges.length 且 startA != startB`

Submission

运行时间: 263 ms

内存: 55.1 MB

class Solution:
    def chaseGame(self, edges: List[List[int]], sta: int, stb: int) -> int:
        n = len(edges)
        g = [[] for _ in range(n)]
        deg = [0] * n

        sta -= 1
        stb -= 1
    
        for u, v in edges:
            u -= 1
            v -= 1
            g[u].append(v)
            g[v].append(u)
            deg[u] += 1
            deg[v] += 1
    
        q = deque()
        for i in range(n):
            if deg[i] == 1:
                q.append(i)
        
        rest = n
        while q:
            u = q.popleft()
            rest -= 1

            for v in g[u]:
                deg[v] -= 1
                if deg[v] == 1:
                    q.append(v)

        def bfs(st: int) -> List[int]:
            q = deque()
            q.append(st)
            dis = [inf] * n
            dis[st] = 0

            while q:
                u = q.popleft()
                for v in g[u]:
                    if dis[v] == inf:
                        dis[v] = dis[u] + 1
                        q.append(v)

            return dis
        
        da = bfs(sta)
        db = bfs(stb)

        ans = 1
        for i in range(n):
            if db[i] < da[i] - 1:
                if rest > 3 and deg[i] > 1:
                    return -1
                ans = max(ans, da[i])
        
        return ans

Explain

该题解首先处理输入的边列表构建了一个无向图，并计算了每个节点的度。接着使用宽度优先搜索（BFS）来计算从起始点sta和stb到每个节点的最短距离。通过比较这两个距离数组，确定是否存在一个位置i使得小扣在小力之前到达且小力无法在下一步直接到达。如果存在这样的点，并且该点不是一个环路中的节点（即度大于1），则返回-1表示小力无法追上小扣。否则，计算小力追上小扣所需的最大距离，即为答案。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def chaseGame(self, edges: List[List[int]], sta: int, stb: int) -> int:
        n = len(edges)
        g = [[] for _ in range(n)]  # 邻接表表示图
        deg = [0] * n  # 节点的度

        sta -= 1  # 转换为0-based索引
        stb -= 1

        for u, v in edges:
            u -= 1
            v -= 1
            g[u].append(v)
            g[v].append(u)
            deg[u] += 1
            deg[v] += 1

        q = deque()  # 用于BFS
        for i in range(n):
            if deg[i] == 1:
                q.append(i)  # 叶子节点加入队列

        rest = n
        while q:  # BFS处理所有节点
            u = q.popleft()
            rest -= 1

            for v in g[u]:
                deg[v] -= 1
                if deg[v] == 1:
                    q.append(v)

        def bfs(st: int) -> List[int]:
            q = deque()
            q.append(st)
            dis = [inf] * n
            dis[st] = 0

            while q:
                u = q.popleft()
                for v in g[u]:
                    if dis[v] == inf:
                        dis[v] = dis[u] + 1  # 更新距离
                        q.append(v)

            return dis

        da = bfs(sta)  # 从sta开始的距离数组
        db = bfs(stb)  # 从stb开始的距离数组

        ans = 1
        for i in range(n):
            if db[i] < da[i] - 1:
                if rest > 3 and deg[i] > 1:
                    return -1  # 小扣可以逃脱
                ans = max(ans, da[i])  # 更新所需最大回合数

        return ans

Explore

在大多数图论问题中，尤其是在算法竞赛或在线编程平台如LeetCode中，题目通常会明确指出是否允许图中存在重复边或自环。通常，除非特别指示，我们假设输入的图不包含重复边和自环。如果题目允许这种情况发生，解题时必须对输入数据进行额外处理，比如使用集合来存储邻接点以避免重复边的影响，或者在添加边时检查是否形成自环。

宽度优先搜索（BFS）是确定无权图中从单一源点到其他所有点的最短路径的最优算法，因为它按层次遍历节点，确保当我们首次访问某节点时，我们已找到从起始点到该节点的最短路径。相比之下，深度优先搜索（DFS）可能会首先沿一条路径深入，不一定能直接找到最短路径。尽管其他算法如Dijkstra或Bellman-Ford也可用于找最短路径，但对于无权图来说，BFS更为简洁且效率更高。

在游戏逻辑中，度数为1的节点（即叶子节点）表示该节点仅与图中一个其他节点相连接。这在逃脱或追捕类游戏中非常关键，因为叶子节点本质上是图的边界，意味着从该节点只有一条路可走。这对策略制定非常重要，例如在追逐游戏中，如果追逐者（小力）追到一个叶子节点，且逃跑者（小扣）已经到达或即将到达那里，逃跑者的逃脱选择将非常有限。因此，叶子节点在确定追逐是否成功或是否存在潜在的逃脱路线时起着重要作用。