2D数组连续元素分组统计算法实现技术咨询

当然有成熟的算法能搞定这个需求！最常用且高效的是深度优先搜索（DFS）或者广度优先搜索（BFS），核心就是找数组中的「连通块」——也就是水平/垂直相连的'X'集合，然后筛选出大小≥4的连通块数量。

具体实现步骤 #

• 步骤1：生成指定尺寸的随机二维数组
  根据用户输入的尺寸n，创建n×n的数组，每个位置随机填充'X'或'O'。

• 步骤2：标记访问状态
  准备一个和原数组同大小的布尔矩阵visited，用来记录哪些位置已经被检查过，避免重复统计同一个连通块。

• 步骤3：遍历数组并搜索连通块
  逐个遍历数组中的每个元素：

  1. 如果当前元素是'X'且未被访问，就启动DFS/BFS探索它的所有相连'X'；
  2. 在搜索过程中，标记所有访问过的'X'，并统计当前连通块的元素数量；
  3. 如果这个连通块的大小≥4，就把有效分组数加1。

• 步骤4：输出结果
  遍历完成后，输出统计到的有效分组数量。

Python代码示例 #

import random

def generate_random_grid(n):
    # 生成n×n的随机X/O数组
    return [[random.choice(['X', 'O']) for _ in range(n)] for _ in range(n)]

def count_valid_x_groups(grid):
    n = len(grid)
    visited = [[False for _ in range(n)] for _ in range(n)]
    valid_groups = 0
    # 定义上下左右四个方向
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    def dfs(row, col):
        # 边界检查：超出数组范围、不是X、已访问，直接返回0
        if row < 0 or row >= n or col < 0 or col >= n or grid[row][col] != 'X' or visited[row][col]:
            return 0
        # 标记为已访问
        visited[row][col] = True
        # 统计当前元素+四个方向的连通元素数量
        count = 1
        for dr, dc in directions:
            count += dfs(row + dr, col + dc)
        return count
    
    # 遍历每个元素
    for i in range(n):
        for j in range(n):
            if grid[i][j] == 'X' and not visited[i][j]:
                group_size = dfs(i, j)
                if group_size >= 4:
                    valid_groups += 1
    return valid_groups

# 示例使用
if __name__ == "__main__":
    n = int(input("请输入二维数组的尺寸："))
    grid = generate_random_grid(n)
    # 打印生成的数组（可选）
    print("生成的随机数组：")
    for row in grid:
        print(' '.join(row))
    # 统计有效分组
    result = count_valid_x_groups(grid)
    print(f"符合条件的X分组数量：{result}")

补充说明 #

• 上面用的是DFS，你也可以换成BFS（用队列实现），逻辑是一样的，只是遍历连通块的方式不同；
• 对角线相连的'X'不会被统计，因为我们只检查了上下左右四个方向；
• 时间复杂度是O(n²)，因为每个元素最多被访问一次，对于n≤1000的数组都能高效运行。

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