T30339: 愉悦的假期

bfs, http://cs101.openjudge.cn/2025fallcs101testing/T30339/

新年&春节假期要来了，陈哥也来到了富人岛上找李哥游玩。

李哥在富人岛群上拥有三座小岛，为了方便，这块海域用一个N*M的矩阵来表示，像这样： ................ ..XXXX....XXX... ...XXXX....XX... .XXXX......XXX.. ........XXXXX... ..XXX....XXX.... 每个 X 表示小岛的一部分。如果两个 X 在竖直或水平方向上相邻，则它们属于同一个小岛（对角线相邻不算），而 . 则表示这里是海水。

陈哥觉得用游艇往来不安全，因此想帮李哥财大气粗地把三座小岛联通，具体来说，就是填海：可以选择将 . 填成陆地 X 。对于上图，下面是一种填海格点数最少的方案： ................ ..XXXX....XXX... ...XXXX*...XX... .XXXX..**..XXX.. .......XXXXX... ..XXX....XXX.... （只填了四个格点，填海的使用来表示）

你知道的，李哥向来喜好省钱，为了他们俩能拥有一个愉悦的假期，所以请你帮陈哥想一个最少填海格点数的方案。

输入

第一行两个整数 N,M（1≤N,M≤50）。接下来 N 行，每行 M 个字符（ . 或 X），描述李哥的小岛在海域内的分布情况。保证恰好有三个小岛。

输出

输出将三个小岛通过填海联通最少需要填多少格点。

样例输入

6 16
................
..XXXX....XXX...
...XXXX....XX...
.XXXX......XXX..
........XXXXX...
..XXX....XXX....

样例输出

提示

友善的陈哥提醒你：

岛之间联通起来的形式只有两种情况
计算一个位置到另一个位置之间的距离可以利用 |xi-xj| + |yi-yj| （即曼哈顿距离，当然你也可以不用）

来源

2025fall-cs101

python

import sys
from collections import deque

# 增加递归深度上限，防止DFS在某些极端情况下爆栈
sys.setrecursionlimit(10000)


def solve():
    # 读取所有输入数据
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    iterator = iter(input_data)
    try:
        # 读取 N 和 M
        N = int(next(iterator))
        M = int(next(iterator))
    except StopIteration:
        return

    # 构建网格地图
    grid = []
    for _ in range(N):
        grid.append(list(next(iterator)))

    # 1. 寻找并标记三个岛屿
    # islands 列表存储三个岛屿各自包含的坐标集合
    islands = []
    visited = [[False] * M for _ in range(N)]

    # 方向数组：上、下、左、右
    dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    # 遍历网格，找到所有的岛屿块
    for r in range(N):
        for c in range(M):
            if grid[r][c] == 'X' and not visited[r][c]:
                # 发现新岛屿，使用BFS将其所有部分找出来
                current_island = []
                q = deque([(r, c)])
                visited[r][c] = True
                current_island.append((r, c))

                while q:
                    cr, cc = q.popleft()
                    for dr, dc in dirs:
                        nr, nc = cr + dr, cc + dc
                        # 检查边界、是否访问过、是否是陆地
                        if 0 <= nr < N and 0 <= nc < M and not visited[nr][nc] and grid[nr][nc] == 'X':
                            visited[nr][nc] = True
                            q.append((nr, nc))
                            current_island.append((nr, nc))
                islands.append(current_island)

    # 题目保证恰好有3个岛屿，如果不是则无需处理
    if len(islands) != 3:
        return

    # 2. 定义计算距离图的函数 (0-1 BFS)
    # 计算地图上任意一点到 start_coords 所在岛屿的最少填海数
    def get_dist_map(start_coords):
        # 初始化距离矩阵为无穷大
        dist = [[float('inf')] * M for _ in range(N)]
        dq = deque()

        # 将岛屿自身的所有点加入队列，距离为0
        for r, c in start_coords:
            dist[r][c] = 0
            dq.append((r, c))

        while dq:
            r, c = dq.popleft()

            for dr, dc in dirs:
                nr, nc = r + dr, c + dc
                if 0 <= nr < N and 0 <= nc < M:
                    # 如果是海(.)，代价为1；如果是陆地(X)，代价为0
                    weight = 1 if grid[nr][nc] == '.' else 0

                    # 如果发现了更短的路径，则更新
                    if dist[r][c] + weight < dist[nr][nc]:
                        dist[nr][nc] = dist[r][c] + weight
                        # 0-1 BFS 优化：权重为0插队首，权重为1插队尾
                        if weight == 0:
                            dq.appendleft((nr, nc))
                        else:
                            dq.append((nr, nc))
        return dist

    # 分别计算三个岛屿到全图的距离
    dist1 = get_dist_map(islands[0])
    dist2 = get_dist_map(islands[1])
    dist3 = get_dist_map(islands[2])

    # 3. 枚举所有可能的交汇点，计算最小代价
    min_fills = float('inf')

    for r in range(N):
        for c in range(M):
            # 获取该点到三个岛屿的距离
            d1 = dist1[r][c]
            d2 = dist2[r][c]
            d3 = dist3[r][c]

            # 只有当三个岛都能到达该点时才计算
            if d1 != float('inf') and d2 != float('inf') and d3 != float('inf'):
                current_cost = d1 + d2 + d3

                # 如果交汇点本身是海，我们在 d1, d2, d3 中都计算了填平这个点的代价(1)
                # 即 1+1+1=3，但实际只需填1次，多算了2次，所以减去2
                if grid[r][c] == '.':
                    current_cost -= 2

                min_fills = min(min_fills, current_cost)

    print(min_fills)


if __name__ == "__main__":
    solve()

T30339: 愉悦的假期 ​

T30339: 愉悦的假期