如何加速处理带单元格翻转的网格连通性查询Python程序以解决超时问题

触发超时的核心原因 #

• 访问节点的检查方式效率极低：原代码用普通列表存已访问坐标，每次判断邻居是否已经访问过，都是遍历整个列表做元素匹配，时间复杂度是线性级别的。当网格规模达到100*100时，这种检查的总耗时会呈平方级增长，是拖慢速度的最主要原因。
• 递归搜索的开销过高：Python中递归函数的栈帧有固定的运行时开销，且递归深度受解释器默认限制，相比迭代实现的搜索，速度差距非常明显。
• 边界判断存在逻辑错误：原代码中做上下移动的边界校验时，错把行号的范围判断套到了列号上，小测试用例碰巧能过，大网格下不仅会出现逻辑错误，也会拖慢判断效率。
• 频繁的IO操作：每处理一次请求就直接调用print输出，print是系统级的IO调用，频繁触发会占用大量运行时间。

针对性优化手段 #

• 把线性的访问检查换成常数时间的数组标记：每次判定路径可达性时，初始化和网格同尺寸的二维标记数组，节点访问过就把对应位置标为1，检查时直接读数组值，一步到位没有额外遍历开销。
• 用迭代BFS替代递归DFS：借助双端队列实现广度优先搜索，从起点开始逐层扩散，只要碰到终点就直接返回可达，遍历完全部可访问节点仍未找到终点就返回不可达，彻底消除递归的额外开销。
• 细节提速：
  • 单元格翻转直接用异或运算grid[x-1][y-1] ^=1替代“加1再模2”的写法，逻辑完全等价且运行更快。
  • 把四个方向的偏移量统一存成常量，消除重复的分支判断代码，减少冗余逻辑。
  • 所有判定结果先存在临时列表里，全部处理完再一次性拼接成字符串输出，把多次IO调用压缩成一次，节省大量时间。

优化后的可直接运行的代码 #

from collections import deque

# 读取初始参数
sx, sy, tx, ty, n, m, q = map(int, input().split())
# 初始化网格：1表示可通行，0表示墙体
grid = []
for _ in range(n):
    row = input().strip()
    grid.append([1 if c == '.' else 0 for c in row])

# 转换为数组下标从0开始的坐标
sx, sy, tx, ty = sx-1, sy-1, tx-1, ty-1
# 上下左右四个方向偏移量
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
output = []

for _ in range(q):
    x, y = map(int, input().split())
    x, y = x-1, y-1
    # 翻转对应单元格的状态
    grid[x][y] ^= 1

    # BFS判断起点到终点的连通性
    visited = [[0]*m for _ in range(n)]
    search_queue = deque([(sx, sy)])
    visited[sx][sy] = 1
    is_connected = False

    while search_queue:
        cur_x, cur_y = search_queue.popleft()
        # 碰到终点直接返回连通
        if cur_x == tx and cur_y == ty:
            is_connected = True
            break
        # 遍历四个方向的邻居
        for dx, dy in directions:
            next_x = cur_x + dx
            next_y = cur_y + dy
            # 检查是否在网格范围内、是否可通行、是否未访问
            if 0 <= next_x < n and 0 <= next_y < m:
                if grid[next_x][next_y] == 1 and not visited[next_x][next_y]:
                    visited[next_x][next_y] = 1
                    search_queue.append((next_x, next_y))
    
    output.append("Yes" if is_connected else "No")

# 一次性输出所有结果
print('\n'.join(output))

优化后的性能表现 #

优化后单次连通性判定的时间复杂度为线性的O(NM)，即便达到题目给定的最大规模（100100网格、100次操作），总运算量也仅在百万级别，在Python解释器下的运行耗时远低于0.5秒的时间限制，可以顺利通过所有测试用例。

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