基于Java的连通分量标记：实现指定大小群组数量统计方法

我来帮你解决这个统计指定大小群组数量的问题，这本质上是经典的连通分量计数场景，用DFS（深度优先搜索）或者BFS（广度优先搜索）都能轻松搞定，下面是详细的实现思路和代码示例：

• 首先需要一个和输入网格同尺寸的访问标记矩阵，用来记录哪些值为1的单元格已经被统计过，避免重复计算同一个群组。
• 遍历整个网格，每当遇到一个未被访问的1时，就用DFS/BFS遍历它所有水平/垂直相邻的1，统计这个群组的总大小。
• 用一个字典来记录每个群组大小对应的出现次数，最后遍历输入的t数组，直接从字典中查询对应大小的计数即可（没有对应大小就返回0）。

def count_group_sizes(grid, t):
    n = len(grid)
    if n == 0:
        return [0] * len(t)
    
    # 初始化访问矩阵，标记单元格是否已被统计
    visited = [[False for _ in range(n)] for _ in range(n)]
    # 存储每个群组大小对应的数量
    size_count = {}
    
    # 定义上下左右四个相邻方向
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    def dfs(i, j):
        # 越界、不是1、已访问的单元格，直接返回0
        if i < 0 or i >= n or j < 0 or j >= n or grid[i][j] != 1 or visited[i][j]:
            return 0
        # 标记当前单元格为已访问
        visited[i][j] = True
        # 初始计数为1（当前单元格）
        count = 1
        # 遍历四个方向，递归统计相邻的1
        for dx, dy in directions:
            count += dfs(i + dx, j + dy)
        return count
    
    # 遍历整个网格的每个单元格
    for i in range(n):
        for j in range(n):
            if grid[i][j] == 1 and not visited[i][j]:
                # 计算当前群组的大小
                group_size = dfs(i, j)
                # 更新字典中的计数
                size_count[group_size] = size_count.get(group_size, 0) + 1
    
    # 生成t数组对应的结果列表
    result = []
    for target in t:
        result.append(size_count.get(target, 0))
    
    return result

如果你的网格尺寸非常大，DFS的递归深度可能会超出Python的默认递归限制，导致栈溢出。这时候用BFS（基于队列的迭代方式）会更稳定：

from collections import deque

def count_group_sizes_bfs(grid, t):
    n = len(grid)
    if n == 0:
        return [0] * len(t)
    
    visited = [[False for _ in range(n)] for _ in range(n)]
    size_count = {}
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    def bfs(i, j):
        # 初始化队列，加入当前单元格
        queue = deque()
        queue.append((i, j))
        visited[i][j] = True
        count = 0
        # 迭代处理队列中的所有单元格
        while queue:
            x, y = queue.popleft()
            count += 1
            # 遍历四个方向的相邻单元格
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                # 检查相邻单元格是否合法、未访问且为1
                if 0 <= nx < n and 0 <= ny < n and grid[nx][ny] == 1 and not visited[nx][ny]:
                    visited[nx][ny] = True
                    queue.append((nx, ny))
        return count
    
    # 遍历网格统计所有群组
    for i in range(n):
        for j in range(n):
            if grid[i][j] == 1 and not visited[i][j]:
                group_size = bfs(i, j)
                size_count[group_size] = size_count.get(group_size, 0) + 1
    
    # 生成结果
    result = [size_count.get(target, 0) for target in t]
    return result

我们用一个具体的网格来测试代码：

# 测试用的4×4网格
grid = [
    [1, 1, 0, 0],
    [1, 1, 0, 1],
    [0, 0, 0, 1],
    [0, 0, 1, 1]
]
# 需要统计的群组大小列表
t = [2, 4, 3]

# 调用DFS版本的函数
print(count_group_sizes(grid, t))  # 输出: [0, 2, 0]

这个示例中，网格里有两个大小为4的群组，所以t中的4对应计数2，其他大小的群组不存在，返回0。

内容的提问来源于stack exchange，提问作者tron