LeetCode「As far from land as possible」超时及循环异常排查

问题描述 #

在完成LeetCode题目"As far from land as possible"时，编写了如下代码，但出现超时（TLE）且首次迭代后grid和dp不再变化，程序陷入无限循环。原本期望当grid所有元素变为1时终止循环，dp用于记录新增的1以避免重复处理，需排查异常原因。

用户代码 #

import numpy as np
class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        counter = 0
        n = len(grid)

        
        while grid.count(1) != n*n:
            dp=np.zeros((n,n))
            print(dp)
            for i in range(n):
                for j in range(n):
                    if grid[i][j] == 1 and not dp[i][j]:
                        if i-1 > 0:
                            grid[i-1][j] = 1
                            dp[i-1][j] = 1
                        if i+1 < n:
                            grid[i+1][j] = 1
                            dp[i+1][j] = 1
                        if j-1 > 0:
                            grid[i][j-1] = 1
                            dp[i][j-1] = 1
                        if j+1 < n:
                            grid[i][j+1] = 1
                            dp[i][j+1] = 1
                        dp[i][j]=1
            counter+=1
            print(grid)
            print("\n")
            print(dp)
        
        return counter  

问题原因分析 #

1. 边界判断错误 #

代码中i-1 > 0、j-1 > 0的条件错误，应该改为i-1 >= 0和j-1 >= 0。原条件会跳过第一行（i=0时i-1=-1不满足>0）和第一列（j=0时j-1=-1不满足>0）的元素，导致这些位置的0永远无法被置为1，循环条件grid.count(1) != n*n永远成立，陷入无限循环。

2. 二维列表的1计数错误 #

grid.count(1)是针对一维列表的计数逻辑，对于二维列表，它只会统计整个子列表等于1的情况，而不是统计所有二维元素中1的总数。比如[[1,0],[0,0]]调用count(1)会返回0，因为没有任何一个子列表是[1]。这导致循环条件的判断完全失效，无法正确识别grid是否全为1。

3. 效率问题导致超时 #

• 使用numpy数组作为dp，但grid是普通Python列表，两者交互会增加额外开销；
• 迭代过程中频繁打印grid和dp，大量IO操作会显著拖慢程序运行速度；
• 逐行逐列遍历的方式效率较低，没有利用多源BFS的高效性，对于较大的输入规模容易超时。

修复方案（多源BFS实现） #

这道题的标准解法是多源广度优先搜索（BFS），初始时将所有陆地（1）加入队列，然后逐层向外扩展海洋（0），记录扩展的层数即为最大距离。

from collections import deque
from typing import List

class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        n = len(grid)
        q = deque()
        
        # 初始化队列，加入所有陆地
        for i in range(n):
            for j in range(n):
                if grid[i][j] == 1:
                    q.append((i, j))
        
        # 如果全是陆地或全是海洋，返回-1
        if len(q) == 0 or len(q) == n * n:
            return -1
        
        directions = [(-1,0), (1,0), (0,-1), (0,1)]
        max_dist = 0
        
        # 多源BFS
        while q:
            level_size = len(q)
            for _ in range(level_size):
                x, y = q.popleft()
                for dx, dy in directions:
                    nx = x + dx
                    ny = y + dy
                    if 0 <= nx < n and 0 <= ny < n and grid[nx][ny] == 0:
                        grid[nx][ny] = 1
                        q.append((nx, ny))
            max_dist += 1
        
        # 最后一次扩展后多加了1，所以减1
        return max_dist - 1

修复说明 #

• 用队列存储初始的所有陆地位置，实现多源同步扩展，避免重复处理；
• 正确统计陆地数量，提前判断全陆地或全海洋的特殊情况；
• 去掉冗余的打印操作和numpy依赖，提升运行效率；
• 边界判断采用0 <= nx < n的标准写法，确保所有位置都能被正确处理。

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