本文共 3435 字，大约阅读时间需要 11 分钟。
为了解决这个问题，我们需要找到最小的天线数目，使得每个点感兴趣的位置都被覆盖。每个天线可以覆盖它所在的位置以及相邻的位置中的一个，根据其方向（北、南、东、西）。
我们可以将问题转化为图的最小顶点覆盖问题，其中每个节点代表一个点感兴趣的位置，边表示两个点可以通过同一个天线被覆盖。我们需要找到最小的顶点集合，使得每个节点至少有一个相邻的节点在这个集合中。
具体步骤如下：
def minimal_antennas(): import sys input = sys.stdin.read data = input().split() index = 0 t = int(data[index]) index += 1 results = [] for _ in range(t): h = int(data[index]) w = int(data[index + 1]) index += 2 grid = [] for i in range(h): grid.append(data[index]) index += 1 stars = [] for i in range(h): for j in range(w): if grid[i][j] == '*': stars.append((i, j)) if not stars: results.append(0) continue covered = [[False for _ in range(w)] for _ in range(h)] dirs = [(-1, 0), (0, 1), (1, 0), (0, -1)] min_antennas = 0 while True: max_cover = 0 best_pos = None found = False for (i, j) in stars: if not covered[i][j]: possible = [] for di, dj in dirs: ni, nj = i + di, j + dj if 0 <= ni < h and 0 <= nj < w: if grid[ni][nj] == '*' and not covered[ni][nj]: possible.append((ni, nj)) if (i, j) in stars: possible.append((i, j)) if not possible: found = True break max_add = 0 best_pos_i, best_pos_j = -1, -1 for (pi, pj) in possible: if covered[pi][pj]: continue add = 1 for di, dj in dirs: ni, nj = pi + di, pj + dj if 0 <= ni < h and 0 <= nj < w: if grid[ni][nj] == '*' and not covered[ni][nj]: add += 1 if add > max_add: max_add = add best_pos_i, best_pos_j = pi, pj if best_pos_i != -1: found = True break if found: min_antennas += 1 for di, dj in dirs: ni, nj = best_pos_i + di, best_pos_j + dj if 0 <= ni < h and 0 <= nj < w: if grid[ni][nj] == '*' and not covered[ni][nj]: covered[ni][nj] = True continue all_covered = True for (i, j) in stars: if not covered[i][j]: all_covered = False break if all_covered: break results.append(min_antennas) for res in results: print(res)minimal_antennas()
该方法通过贪心算法尽可能高效地覆盖所有点感兴趣的位置，确保最小的天线数目。
转载地址：http://dbxfk.baihongyu.com/