无向图劫匪逃生与警方抓捕博弈：第一变体算法求解

Let's tackle this cops-and-robbers graph game problem head-on. I'll break down the core logic, key observations, and a step-by-step algorithm to determine if the robbers can secure a win under the first variant rules.

First, let's formalize the rules to avoid ambiguity:

• Graph Setup: Undirected graph with 4 vertex types: robbers (R), cops (P), empty nodes, and magic exits (M).
• Movement Rules:
  • Robbers and cops move along edges at unit speed.
  • Robbers reach a magic exit → they're safe.
  • Cops cannot enter magic exits.
  • If a cop and robber occupy the same vertex (at any point after movement), the robber is captured.
• Turn Order: Robbers move first, turns alternate strictly. At least one side must move each turn.
• Win/Loss/Draw Conditions (Variant 1):
  • Robbers Win: All robbers reach any magic exit.
  • Cops Win: All robbers are captured.
  • Draw: Any other scenario (e.g., partial captures, endless cyclic movement).

Before diving into the algorithm, let's lock in critical insights from optimal play:

• Robber Priority: Each robber's best move is to take the shortest path to the nearest magic exit—any detour would only give cops more time to intercept.
• Cop Priority: Cops will focus on intercepting the robber closest to an exit first; letting that robber escape makes a cop win impossible.
• First-Mover Advantage: Since robbers act first, their step count to an exit has a slight edge over cops' intercept steps. For example: a robber needing 2 steps will reach the exit on their second turn, while cops only get 1 turn to move before that.

We'll use BFS (ideal for unweighted graphs) to compute shortest paths, then evaluate each robber's escape potential against cop intercept capabilities.

Step 1: Precompute All Required Distances #

Use BFS to calculate:

• For each robber, the shortest distance to every magic exit. Track the minimum distance (min_dist_r) to their closest exit.
• For each cop, the shortest distance to every non-exit node (since cops can't enter magic exits).
• For each magic exit, the shortest distance from cops to its adjacent nodes (the last possible intercept point before a robber escapes).

Step 2: Evaluate Individual Robber Escape Potential #

For each robber r:

1. If min_dist_r is infinite (no exit exists in their connected component), this robber can't escape. Check if cops can reach them (if yes, they'll be captured; if no, this leads to a draw).
2. For their closest exit m:
   • Calculate the minimum number of steps any cop needs to reach a neighbor of m (the final intercept point). Let's call this min_cop_steps.
   • Escape Check: Since robbers move first, a robber can escape if min_dist_r ≤ min_cop_steps. Here's why:
     • The robber takes min_dist_r turns to reach the exit.
     • Cops only get min_dist_r - 1 turns to move before the robber escapes. If cops need more than min_dist_r - 1 steps to reach the intercept point, they can't stop the robber.

Step 3: Determine Global Outcome #

• Robbers Win: Every robber has at least one exit they can reach before any cop can intercept them.
• Cops Win: Every robber either can't reach an exit, or every possible exit path is interceptable by cops before they escape.
• Draw: At least one robber can escape, and at least one robber can't escape (or can be captured, but not all).

Don't forget these edge scenarios that can break naive logic:

• Robber starts on an exit: This robber is already safe—only evaluate the remaining robbers.
• Cop starts adjacent to a robber: The robber can move away on their first turn (if there's a path) to avoid immediate capture.
• Disconnected graph: A robber in a component without exits can never escape; if cops can't reach that component either, it's a draw.
• No exits: Robbers can never win—cops win only if they can capture all robbers; else, draw.

Here's a BFS-based code snippet to implement the logic:

from collections import deque

def bfs(graph, start, forbidden_nodes):
    """Compute shortest distances from start to all reachable nodes, skipping forbidden nodes."""
    node_count = len(graph)
    distances = [-1] * node_count
    queue = deque()
    
    if start not in forbidden_nodes:
        distances[start] = 0
        queue.append(start)
    
    while queue:
        current = queue.popleft()
        for neighbor in graph[current]:
            if neighbor not in forbidden_nodes and distances[neighbor] == -1:
                distances[neighbor] = distances[current] + 1
                queue.append(neighbor)
    
    return distances

def determine_game_outcome(graph, robbers, cops, exits):
    # Precompute each robber's shortest distance to any exit
    robber_exit_dists = []
    exit_set = set(exits)
    for robber in robbers:
        dists = bfs(graph, robber, set())
        valid_dists = [dists[exit_node] for exit_node in exits if dists[exit_node] != -1]
        min_dist = min(valid_dists) if valid_dists else float('inf')
        robber_exit_dists.append(min_dist)
    
    # Precompute each cop's distances to non-exit nodes
    cop_distances = [bfs(graph, cop, exit_set) for cop in cops]
    
    all_robbers_escape = True
    all_robbers_captured = True
    
    for idx, robber in enumerate(robbers):
        min_dist_r = robber_exit_dists[idx]
        
        # Case 1: Robber can't reach any exit
        if min_dist_r == float('inf'):
            all_robbers_escape = False
            # Check if any cop can reach this robber
            cop_can_reach = False
            for cop_dist in cop_distances:
                if cop_dist[robber] != -1:
                    cop_can_reach = True
                    break
            if not cop_can_reach:
                all_robbers_captured = False
            continue
        
        # Case 2: Check if robber can escape to any closest exit
        can_escape = False
        # Get all exits at min distance from robber
        dists_to_exits = bfs(graph, robber, set())
        closest_exits = [m for m in exits if dists_to_exits[m] == min_dist_r]
        
        for exit_node in closest_exits:
            # Find minimum cop steps to reach any neighbor of the exit
            min_cop_to_neighbor = float('inf')
            for neighbor in graph[exit_node]:
                if neighbor in exit_set:
                    continue
                for cop_dist in cop_distances:
                    if cop_dist[neighbor] != -1 and cop_dist[neighbor] < min_cop_to_neighbor:
                        min_cop_to_neighbor = cop_dist[neighbor]
            # Escape condition: robber's steps <= cop's steps (due to first-mover advantage)
            if min_dist_r <= min_cop_to_neighbor:
                can_escape = True
                break
        
        if can_escape:
            all_robbers_captured = False
        else:
            all_robbers_escape = False
    
    if all_robbers_escape:
        return "Robbers Win"
    elif all_robbers_captured:
        return "Cops Win"
    else:
        return "Draw"

内容的提问来源于stack exchange，提问作者Shridhar R Kulkarni