本文共 3254 字，大约阅读时间需要 10 分钟。
为了解决这个问题，我们需要找到一种方法来估算Borg搜索迷宫的最小成本。迷宫中隐藏着多个外星人（用 'A' 表示），我们需要从起点 'S' 出发，找到所有外星人的最短路径，并确保总成本最小。
问题分析：迷宫由空格、墙、外星人和起点组成。目标是从起点找到所有外星人的最短路径，总成本是所有路径的总和。由于迷宫的周围是封闭的，起点不会逃逸。
图论建模：将外星人和起点视为图中的节点，节点之间的边权重是它们之间的最短路径距离。问题转化为找到最小生成树，使得所有节点连接的总权重最小。
算法选择：使用Kruskal算法来构建最小生成树，它适合处理权重从小到大排序的边，并确保不形成环。
步骤：
import sysfrom collections import dequedef 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/