LINQ合并多列表及《Skynet Revolution Episode 2》关卡技术咨询

Core Problem Recap #

You’re tasked with blocking an agent from reaching any gateway node each turn by cutting only one direct connection to a gateway. The key challenges we’ll tackle here are:

1. Efficiently identifying all critical gateway-neighbor connections
2. Merging multiple connection lists using LINQ
3. Choosing the optimal connection to cut each turn

1. Merging Gateway Connection Lists with LINQ #

Since each gateway (a Node instance) has its own Connections list of direct neighbors, LINQ’s SelectMany is perfect for flattening all these nested lists into a single collection of nodes connected to any gateway. This simplifies analyzing all potential connections to cut.

Example: Flatten All Gateway Neighbors #

// Assuming gateways is your List<Node> of gateway nodes
var allGatewayConnectedNodes = gateways.SelectMany(gateway => gateway.Connections);

Example: Get Unique Gateway Connections (Avoid Duplicates) #

If you want to represent each unique connection (since a connection between gateway G and node X is identical to X and G), create a helper struct to standardize connection pairs, then use Distinct:

// Helper struct to represent unique connections consistently
public readonly struct Connection
{
    public int NodeA { get; }
    public int NodeB { get; }

    public Connection(int node1, int node2)
    {
        // Store IDs in ascending order to eliminate duplicate pairs like (G,X) and (X,G)
        NodeA = Math.Min(node1, node2);
        NodeB = Math.Max(node1, node2);
    }
}

// Merge and deduplicate all gateway connections
var uniqueGatewayConnections = gateways
    .SelectMany(gateway => gateway.Connections
        .Select(neighbor => new Connection(gateway.Id, neighbor.Id)))
    .Distinct();

2. Identifying the Optimal Connection to Cut #

The most effective strategy is to cut the connection that lies on the shortest path from the agent to any gateway. This blocks the agent’s fastest route to a gateway. Use BFS (Breadth-First Search) to find this critical connection quickly.

Step 1: Find the Node Adjacent to the Closest Gateway #

private Node GetNodeAdjacentToClosestGateway(Node agentCurrentNode, List<Node> gateways)
{
    var visited = new HashSet<Node>();
    var queue = new Queue<(Node current, Node previousNode)>();
    
    queue.Enqueue((agentCurrentNode, null));
    visited.Add(agentCurrentNode);

    while (queue.Count > 0)
    {
        var (current, previous) = queue.Dequeue();

        // Check if current node is a gateway
        if (gateways.Contains(current))
        {
            // Return the node directly connected to this gateway in the shortest path
            return previous;
        }

        // Explore all unvisited neighbors
        foreach (var neighbor in current.Connections.Where(n => !visited.Contains(n)))
        {
            visited.Add(neighbor);
            queue.Enqueue((neighbor, current));
        }
    }

    // Edge case: No gateway found (shouldn't occur in valid game states)
    return null;
}

Step 2: Cut the Connection & Output the Command #

Once you have the node adjacent to the closest gateway, remove the connection from both nodes' lists and output the cut command as required by CodinGame:

// Fetch the agent's current position from CodinGame's input each turn
Node agentCurrentNode = /* Your logic to retrieve the agent's node */;

var nodeToCut = GetNodeAdjacentToClosestGateway(agentCurrentNode, gateways);
var closestGateway = gateways.First(g => g.Connections.Contains(nodeToCut));

// Remove the connection from both nodes to keep the network state accurate
nodeToCut.Connections.Remove(closestGateway);
closestGateway.Connections.Remove(nodeToCut);

// Output the cut command (CodinGame expects "nodeId gatewayId")
Console.WriteLine($"{nodeToCut.Id} {closestGateway.Id}");

Key Notes #

• LINQ Efficiency: SelectMany is ideal for flattening nested lists, and pairing it with Distinct ensures you only process each unique connection once.
• BFS for Shortest Path: BFS guarantees the shortest path in unweighted graphs (like this network), making it the fastest way to find the critical connection to cut.
• Connection Removal: Always remove the connection from both nodes' Connections lists to maintain an accurate network state for subsequent turns.

内容的提问来源于stack exchange，提问作者abinmorth