Python求解岛屿周长BFS实现出现时间超限问题

给定大小为row x col的网格表示地图，计算岛屿周长的规则如下：

• grid[i][j] = 1代表陆地，grid[i][j] = 0代表水域
• 网格单元格仅支持水平/垂直方向连通（斜向不连通）
• 整个网格被水域完全包围，地图中恰好存在一座岛屿（由一个或多个互相连通的陆地单元格构成）
• 岛屿内部不存在“湖泊”，即岛屿内部包裹的水域不与网格外围的水域连通
• 每个单元格为边长1的正方形，网格为矩形，宽、高均不超过100

示例1 #

• 输入：grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
• 输出：16
• 说明：周长对应示意图中的16条黄色边
  

islandPerimeter()为解题核心函数，实现思路为从(0,0)单元格出发BFS遍历网格，每遇到陆地单元格周长计数加4，每检测到一对相邻陆地则周长计数减1：

def islandPerimeter(self, grid: List[List[int]]) -> int:
    v=[[0,0]]
    q=[[0,0]]
    c=0
    return self.bfs(grid,v,q,c)

def bfs(self,grid,v,q,c):
    if q==[]:
        return c
    i=q[0][0]
    j=q[0][1]
    if grid[i][j]:
        c+=4
    if i-1 > -1:
        if [i-1,j] not in v:
            q.append([i-1,j])
            v.append([i-1,j])
        if grid[i-1][j] and grid[i][j]:
            c-=1
    if j-1 > -1:
        if [i,j-1] not in v:
            q.append([i,j-1])
            v.append([i,j-1])
        if grid[i][j-1] and grid[i][j]:
            c-=1
    try:
        a=grid[i+1][j]
        if [i+1,j] not in v:
            q.append([i+1,j])
            v.append([i+1,j])
        if grid[i+1][j] and grid[i][j]:
            c-=1
    except:
        pass
    try:
        a=grid[i][j+1]
        if [i,j+1] not in v:
            q.append([i,j+1])
            v.append([i,j+1])
        if grid[i][j+1] and grid[i][j]:
            c-=1
    except:
        pass
    del q[0]

    return self.bfs(grid,v,q,c)

代码中变量定义：

• q：BFS使用的遍历队列
• v：已访问单元格标记数组
• i：行索引
• j：列索引
• c：周长计算结果

提交后运行触发**时间限制超出（Time Limit Exceeded）**错误，根因如下：

1. 已访问标记判断时间复杂度爆炸
   用列表v存储已访问坐标，每次执行[x,y] not in v时，需要从头到尾线性扫描整个列表匹配元素，单次操作时间复杂度为O(k)（k为已访问元素总数）。网格最大尺寸为100*100=10000个单元格，仅这部分操作的总时间复杂度就达到O(n²)，是超时的核心原因。
2. 队列操作效率极低
   用普通列表实现队列，通过del q[0]删除队首元素时，需要将列表中后续所有元素向前移动一位，单次操作时间复杂度为O(k)，全程BFS下来这部分开销同样达到O(n²)量级。
3. 冗余逻辑进一步放大性能开销
   从(0,0)点开始全网格遍历所有水域和陆地，而题目明确说明只有一座岛屿，完全可以先定位到第一个陆地单元格再开始BFS，省去遍历所有水域的无效开销；另外用try/except做边界判断的写法，异常捕获的性能开销远高于直接用坐标范围判断，在循环中会进一步拖慢运行速度。

• 替换访问标记结构：用和网格同尺寸的二维布尔数组存储访问状态，单次访问判断时间复杂度降为O(1)；也可以直接把访问过的陆地单元格值改为0，省去额外的标记数组空间。
• 替换队列实现：用collections.deque作为BFS队列，调用popleft()方法弹出队首，单次操作时间复杂度为O(1)。
• 优化遍历起点：先遍历网格找到第一个值为1的陆地单元格，从该点开始BFS，仅遍历陆地连通块，遇到边界或水域就累加对应边长，减少无效遍历。
• 去掉异常捕获的边界判断，直接通过坐标是否在[0, rows)、[0, cols)范围内判断越界。

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