Python解决Hackerearth Bomb Game超时问题优化求助

你正在玩一个游戏，游戏中有一个n*n的矩形网格。每个单元格要么是空的（标记为.），要么有一个烟花（标记为*）。相邻单元格指共享一条边的单元格。
如果任意单元格中的烟花爆炸，会摧毁自身以及所有与它连通的空单元格（连通指存在相邻空单元格组成的路径）。需要计算所有烟花分别独立触发时，总共被摧毁的单元格数量。

输入格式：

• 第一行是整数n，表示网格尺寸
• 接下来n行每行n个符号，.为空，*为烟花

输出格式：输出总摧毁单元格数

输入约束：1 ≤ n ≤ 100

示例输入：

4
*..*
..*.
*..*
*..*

示例输出：66

原代码能通过部分测试用例，但n≥100时超时，原代码如下：

n = int(input())
grid = [input() for i in range(n)]
count = 0
def dfs(i, j):
    if i < 0 or i >= n or j < 0 or j >= n or visited[i][j] or grid[i][j] == "*":
        return 0
    visited[i][j] = True
    return 1 + dfs(i + 1, j) + dfs(i - 1, j) + dfs(i, j + 1) + dfs(i, j - 1)
for i in range(n):
    for j in range(n):
        if grid[i][j] == "*":
            visited = [[False for _ in range(n)] for _ in range(n)]
            count += dfs(i + 1, j) + dfs(i - 1, j) + dfs(i, j + 1) + dfs(i, j - 1) + 1
print(count)

请问如何优化这段代码以提升运行速度？

核心思路：避免重复计算 #

原代码的问题是每个烟花都重新遍历一次连通区域，时间复杂度为O(k*n²)（k是烟花数量），当n=100时，k最多达到10000，总操作数会升至1e8量级，容易超时。优化方向是预计算所有空单元格的连通分量，记录每个分量的大小，再快速统计每个烟花能覆盖的分量总和。

具体步骤：

1. 标记连通分量：遍历网格，对所有未访问的空单元格用BFS/DFS标记所属连通分量，并记录每个分量的大小。
2. 统计单烟花摧毁数：对每个烟花，收集其四个相邻方向的空单元格对应的连通分量（用集合去重，避免重复计算同一分量），将分量大小相加后加1（烟花自身）。
3. 累加总摧毁数：将所有烟花的摧毁数相加得到最终结果。

优化后的代码 #

n = int(input())
grid = [input() for _ in range(n)]

# 连通分量标记数组，-1表示未访问
component_id = [[-1 for _ in range(n)] for _ in range(n)]
component_size = []
current_id = 0

# 四个移动方向
dirs = [(-1,0), (1,0), (0,-1), (0,1)]

def bfs(i, j):
    queue = [(i, j)]
    component_id[i][j] = current_id
    size = 1
    while queue:
        x, y = queue.pop(0)
        for dx, dy in dirs:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < n and 0 <= ny < n and component_id[nx][ny] == -1 and grid[nx][ny] == '.':
                component_id[nx][ny] = current_id
                size += 1
                queue.append((nx, ny))
    return size

# 遍历网格，标记所有连通分量
for i in range(n):
    for j in range(n):
        if grid[i][j] == '.' and component_id[i][j] == -1:
            size = bfs(i, j)
            component_size.append(size)
            current_id += 1

total = 0

# 计算每个烟花的摧毁数
for i in range(n):
    for j in range(n):
        if grid[i][j] == '*':
            components = set()
            for dx, dy in dirs:
                nx = i + dx
                ny = j + dy
                if 0 <= nx < n and 0 <= ny < n and grid[nx][ny] == '.':
                    components.add(component_id[nx][ny])
            bomb_destroy = 1
            for cid in components:
                bomb_destroy += component_size[cid]
            total += bomb_destroy

print(total)

优化效果说明 #

• 时间复杂度降至O(n²)：仅需两次遍历网格，总操作数为O(n²)级别，n=100时仅1e4次操作，远低于原代码的1e8次。
• 用BFS替代DFS：避免递归深度过大的潜在问题，同时运行效率稳定。
• 去重处理：通过集合确保同一连通分量不会被重复计算，保证结果准确。

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