本文共 3336 字，大约阅读时间需要 11 分钟。

为了解决这个问题，我们需要找到一种方法来估算Borg搜索迷宫的最小成本。迷宫中隐藏着多个外星人（用 'A' 表示），我们需要从起点 'S' 出发，找到所有外星人的最短路径，并确保总成本最小。

方法思路

解决代码

import sys
from collections import deque
def main():
    input = sys.stdin.read().split()
    ptr = 0
    t = int(input[ptr])
    ptr += 1
    for _ in range(t):
        n = int(input[ptr])
        m = int(input[ptr+1])
        ptr +=2
        map = []
        a = []
        for i in range(n):
            line = input[ptr]
            ptr +=1
            map.append(list(line))
            for j in range(m):
                if map[i][j] == 'S':
                    sx, sy = i+1, j+1
                elif map[i][j] == 'A':
                    a.append( (i+1, j+1) )
        # Create nodes: S is 1, A's are 2..n, n+1 is dummy
        # Each A is a node, S is node 1
        node_num = len(a) +1
        # Compute distances from S to each A
        # BFS for each A
        # Create a graph where edge between u and v is the distance
        edges = []
        for u in range(1, node_num+1):
            if u ==1:
                continue
            x, y = a[u-2]
            visited = [[False]*(m+1) for _ in range(n+1)]
            q = deque()
            q.append( (x, y, 0) )
            visited[x][y] = True
            dist = { }
            dist[(x,y)] = 0
            while q:
                cx, cy, d = q.popleft()
                for dx, dy in [(-1,0),(1,0),(0,-1),(0,1)]:
                    nx = cx + dx
                    ny = cy + dy
                    if 1<=nx<=n and 1<=ny<=m and not visited[nx][ny] and map[nx-1][ny-1] != '#':
                        visited[nx][ny] = True
                        q.append( (nx, ny, d+1) )
                        dist[(nx, ny)] = d+1
            # Now, for this A, add edges from 1 to it
            # And edges between other As if needed
            for v in range(2, node_num+1):
                if u ==v:
                    continue
                if (u, v) not in edges and (v, u) not in edges:
                    edges.append( (min(u,v), max(u,v), dist.get( (u, v), float('inf')) ) )
        # Now, Kruskal's algorithm
        # Sort edges by weight
        edges.sort(key=lambda x: x[2])
        # Disjoint Set Union
        parent = list(range(node_num +1))
        def find(u):
            while parent[u] != u:
                parent[u] = parent[parent[u]]
                u = parent[u]
            return u
        def union(u, v):
            u_root = find(u)
            v_root = find(v)
            if u_root == v_root:
                return False
            parent[v_root] = u_root
            return True
        total =0
        count =0
        for u, v, w in edges:
            if union(u, v):
                total +=w
                count +=1
                if count == node_num-1:
                    break
        print(total)
if __name__ == "__main__":
    main()

代码解释

通过这种方法，我们能够有效地找到迷宫中所有外星人的最短路径总和，确保总成本最小。

转载地址：http://kfxfk.baihongyu.com/