Very simple Python BFS, But Why TLE??


  • 16
    A

    I thought it is a straightforward BFS search, so I write it like the following.
    Actually, I have the same question with Number of Island problem:
    https://discuss.leetcode.com/topic/88586/why-python-bfs-get-time-exceed-error

    import collections
    class Solution(object):
        def cutOffTree(self, G):
            """
            :type forest: List[List[int]]
            :rtype: int
            """
            if not G or not G[0]: return -1
            m, n = len(G), len(G[0])
            trees = []
            for i in xrange(m):
                for j in xrange(n):
                    if G[i][j] > 1:
                        trees.append((G[i][j], i, j))
            trees = sorted(trees)
            count = 0
            cx, cy = 0, 0
            for h, x, y in trees:
                step = self.BFS(G, cx, cy, x, y)
                if step == -1:
                    return -1
                else:
                    count += step
                    G[x][y] = 1
                    cx, cy = x, y
            return count
    
        def BFS(self, G, cx, cy, tx, ty):
            m, n = len(G), len(G[0])
            visited = [[False for j in xrange(n)] for i in xrange(m)]
            Q = collections.deque()
            step = -1
            Q.append((cx, cy))
            while len(Q) > 0:
                size = len(Q)
                step += 1
                for i in xrange(size):
                    x, y = Q.popleft()
                    visited[x][y] = True
                    if x == tx and y == ty:
                        return step
                    for nx, ny in [(x + 1, y), (x - 1, y), (x, y-1), (x, y + 1)]:
                        if nx < 0 or nx >= m or ny < 0 or ny >= n or G[nx][ny] == 0 or visited[nx][ny]:
                            continue
                        Q.append((nx, ny))
            return -1
    

  • 2
    Y
    visited[x][y] = True 
    

    should be put in

    for nx, ny in [(x + 1, y), (x - 1, y), (x, y-1), (x, y + 1)]:
                        if nx < 0 or nx >= m or ny < 0 or ny >= n or G[nx][ny] == 0 or visited[nx][ny]:
                            continue
                        Q.append((nx, ny))
                        The visited[x][y] = True
    

    if you put it there, you might visite the position many times. And that leads to TLE.
    I just have the same problem with you.


  • 0

    Same problem here. I think the time allowed for this question for python is not correct.


  • 1
    N

    def BFS(self, G, cx, cy, tx, ty):

    If you need to do BFS from (cx,cy) to (tx,ty), instead of doing BFS from (cx,cy) only, you can do two-way BFS both from (cx,cy) and (tx,ty).

    For example, to find the minimum step from C to T, X is obstacle.
    Doing two-way BFS step by step:

        [C, , , ]
        [ , ,X, ]  
        [ ,X, , ] 
        [ ,X, ,T] 
    
        [0,1, , ]
        [1, ,X, ]  
        [ ,X, ,1] 
        [ ,X,1,0] 
    
        [0,1,2, ]
        [1,2,X,2]  
        [2,X,2,1] 
        [ ,X,1,0] 
    
        [0,1,2,3] <--- two BFS meet '3' here 
        [1,2,X,2]  
        [2,X,2,1] 
        [3,X,1,0] 
    

    step = 3+3 = 6
    I think it works faster.


  • 1
    N

    Another optimization is, saying you are cutting tree from height 5 to height 6, and the next tree after 6 is 7, after finding the shortest path from 5 to 6, if 7 is within the shortest path, then you don't need to do another BFS from 6 to 7 again.

    Shortest path from 5->6 :
    5 --(4 step)--> 7 --(6 step)--> 6
    5 -> 6 : 10 step
    6 -> 7 must be 6 step.


  • 5
    M

    I kept getting TLE during the contest, too. I went through the top 50 people's code after the contest, and it seemed that none of them used Python. I think the allowed time is unfair for Python programmers.

    Note: I did set visited[x][y] = True before putting x,y into the queue.


  • 0
    Y

    @niwota Hi, I tried two-way BFS and it still says TLE..


  • 0
    A

    @yuchengtang94
    I tried to set the visited flag before adding it into the queue, i still get TLE...


  • 0
    M

    Did anyone get accepted using Python?


  • 2

    @mainarke Nobody during the contest, two people after the contest. One in their eleventh attempt (four of the failures were TLE) and the other in their fifth attempt (three of the failures were TLE).


  • 0
    M

    @StefanPochmann Thanks!


  • 2

    @StefanPochmann Actually, the first "solver" doesn't have a real solution, their code starts with if forest[0][0] == 46362: return 65669 and two more of those.

    But the second solver's solution is legitimate. It does do independent shortest-path searches from each tree to the next, but uses something somewhat better than BFS (and some optimizations). An algorithm I didn't know before, and which is quite interesting. I asked them to share it here in the forum.

    And now a third person did it but cheated just like the first (at least in the few submissions I checked, they submitted so many I'm not going to check all of them).


  • 0
    M

    @StefanPochmann Thanks for the information. Looking forward to the brilliant solution from the second solver.


  • 0

  • 0
    M

    @StefanPochmann Thanks. I am reading it now. Interesting A* algorithm.


Log in to reply
 

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