Why Python BFS get Time Exceed Error?


  • 0
    A

    I use a typical BFS solution, but get a TLE error. It looks the python time limit is set too tight?
    Any comments to the reason?

    from Queue import deque
    class Solution(object):
        def numIslands(self, G):
            """
            :type grid: List[List[str]]
            :rtype: int
            """
            M = len(G)
            if M == 0: return 0
            N = len(G[0])
            if N == 0: return 0
            count = 0
            for i in range(M):
                for j in range(N):
                    if G[i][j] == '1':
                        count += 1
                        self.flood(G, i, j)
            return count
    
        def flood(self, G, r, c):
            M, N = len(G), len(G[0])
            Q = deque()
            Q.append((r, c))
            while len(Q):
                top = Q.popleft()
                i, j = top[0], top[1]
                G[i][j] = ' '
                if i - 1 >= 0 and G[i - 1][j] == '1':
                    Q.append((i - 1, j))
                if i + 1 < M and G[i + 1][j] == '1':
                    Q.append((i + 1, j))
                if j - 1 >= 0 and G[i][j - 1] == '1':
                    Q.append((i, j - 1))
                if j + 1 < N and G[i][j + 1] == '1':
                    Q.append((i, j + 1))
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.