本文共 2763 字，大约阅读时间需要 9 分钟。
为了解决这个问题，我们需要找到两个起点，使得从这两个起点同时点燃的火焰能够在最短的时间内烧掉所有的草。火焰可以水平、垂直相邻的四个方向扩散。我们需要计算这种情况下的最小时间，如果无法完全烧掉所有的草，则返回-1。
import sysfrom collections import dequedef solve(): T = int(sys.stdin.readline()) for case in range(1, T + 1): N, M = map(int, sys.stdin.readline().split()) grid = [] for _ in range(N): row = sys.stdin.readline().strip() grid.append(row) # 收集所有'#'的位置 cells = [] for i in range(N): for j in range(M): if grid[i][j] == '#': cells.append((i, j)) num_cells = len(cells) if num_cells == 0: print(-1) continue if num_cells == 1: print(0) continue # 初始化最小时间为一个很大的值 min_time = float('inf') # 遍历所有可能的起点对 for i1, j1 in cells: for i2, j2 in cells: # 创建一个距离矩阵，初始化为-1 distance = [[-1 for _ in range(M)] for _ in range(N)] # 初始化队列，同时加入两个起点 queue = deque() queue.append((i1, j1)) distance[i1][j1] = 0 queue.append((i2, j2)) distance[i2][j2] = 0 # BFS开始 while queue: x, y = queue.popleft() # 四个方向 for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]: nx = x + dx ny = y + dy if 0 <= nx < N and 0 <= ny < M: if distance[nx][ny] == -1 and grid[nx][ny] == '#': distance[nx][ny] = distance[x][y] + 1 queue.append((nx, ny)) # 检查是否覆盖所有细胞 all_covered = True max_dist = 0 for (a, b) in cells: if distance[a][b] == -1: all_covered = False break if distance[a][b] > max_dist: max_dist = distance[a][b] if all_covered: if max_dist < min_time: min_time = max_dist if min_time != float('inf'): print(min_time) else: print(-1)if __name__ == "__main__": solve() 通过这种方法，我们可以高效地解决问题，确保在最短的时间内找到最优解。
转载地址：http://emziz.baihongyu.com/