最少选择使得三个地方连成一片

Question

求完整代码写一下

描述：

人工智能高度发达的时代，拟举办人工智能创意编程大赛。
该赛事由科技馆、教育局、进修学校协同组织举办。
小红帽为此，经常要去这三个地方进行沟通协调。为了高效，请您规划并创建专用“道路”，让这三个地方“联”成一片。

规定如下：

地图由n行m列构成。1表示科技馆所在地，2表示教育局所在地，3表示进修学校所在地，#表示这个地方不可通行，.表示这个地方可以通行。
为了不造成过多的干扰，您需要选择最少.使得三个地方联成一片。
输入
第一行为n,m(1≤n, m≤1000)

接下来n行，每行有m个字符，1表示科技馆所在地，2表示教育局所在地，3表示进修学校所在地，#表示这个地方不可通行，.表示这个地方可以通行。

输出
如果这三个地方无论如何都不能到达，输出-1。否则输出至少需要占用多少个.

输入样例 1

4 5
11..2
#..22
#.323
##333

输出样例 1

2

Answer 1

🕒下午好，题主！目前：🟢[在线]
📢参考通义千问、由郭老师整理提供！
📣今日诗号：愿我如星君如月，夜夜流光相皎洁。

from collections import deque

def bfs(grid, start_x, start_y, end_x, end_y):
  """
  使用广度优先搜索 (BFS) 算法找到从起点到终点的最短路径。

  参数:
      grid: 地图网格，一个二维列表。
      start_x: 起点的 x 坐标。
      start_y: 起点的 y 坐标。
      end_x: 终点的 x 坐标。
      end_y: 终点的 y 坐标。

  返回值:
      如果找到路径，则返回路径长度；否则返回 -1。
  """

  n = len(grid)
  m = len(grid[0])

  # 定义四个方向的移动
  dx = [0, 0, 1, -1]
  dy = [1, -1, 0, 0]

  # 创建一个队列来存储待探索的节点
  queue = deque([(start_x, start_y, 0)])

  # 创建一个集合来存储已经访问过的节点
  visited = set([(start_x, start_y)])

  while queue:
    x, y, distance = queue.popleft()

    # 如果到达终点，则返回距离
    if x == end_x and y == end_y:
      return distance

    # 探索四个方向的相邻节点
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]

      # 检查相邻节点是否有效
      if 0 <= nx < n and 0 <= ny < m and grid[nx][ny] != '#' and (nx, ny) not in visited:
        queue.append((nx, ny, distance + 1))
        visited.add((nx, ny))

  # 如果没有找到路径，则返回 -1
  return -1


# 读取输入
n, m = map(int, input().split())
grid = []
for _ in range(n):
  grid.append(list(input()))

# 找到三个地点的坐标
locations = []
for i in range(n):
  for j in range(m):
    if grid[i][j] in ['1', '2', '3']:
      locations.append((i, j))

# 计算两两地点之间的最短路径
distances = []
for i in range(len(locations)):
  for j in range(i + 1, len(locations)):
    x1, y1 = locations[i]
    x2, y2 = locations[j]
    distance = bfs(grid, x1, y1, x2, y2)
    distances.append(distance)

# 如果任何两个地点之间都没有路径，则输出 -1
if any(distance == -1 for distance in distances):
  print(-1)
else:
  # 找到连接三个地点所需的最短路径长度
  min_distance = min(distances)
  print(min_distance)

代码解释:

1. 输入处理:

   • 读取地图的大小 n 和 m。
   • 读取地图数据，存储在二维列表 grid 中。
   • 找到三个地点（科技馆、教育局、进修学校）的坐标，存储在 locations 列表中。

2. 广度优先搜索 (BFS):

   • bfs 函数使用 BFS 算法找到从起点到终点的最短路径长度。
   • 它维护一个队列，存储待探索的节点及其距离。
   • 它还使用一个集合来跟踪已访问的节点，以避免重复访问。
   • 对于每个节点，它探索四个方向上的相邻节点，并检查它们是否有效（在地图范围内、不是障碍物、尚未访问过）。
   • 如果找到终点，则返回到终点的距离；否则，继续搜索，直到队列为空。

3. 计算最短路径:

   • 遍历 locations 列表中的所有地点对。
   • 对于每对地点，调用 bfs 函数计算它们之间的最短路径长度。
   • 将所有计算出的距离存储在 distances 列表中。

4. 输出结果:

   • 如果 distances 列表中存在 -1，则表示至少有一对地点之间没有路径，因此输出 -1。
   • 否则，找到 distances 列表中的最小值，即连接三个地点所需的最少 "." 数量，并输出该值。

示例输入和输出:

输入:

4 5
11..2
#..22
#.323
##333

输出:

2

这表示需要添加 2 个 "." 才能将三个地点连接起来。