本文共 3514 字，大约阅读时间需要 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/