6 lines O(mn) Python BFS


  • 22

    Some hacks, but whatever.

    def wallsAndGates(self, rooms):
        q = [(i, j) for i, row in enumerate(rooms) for j, r in enumerate(row) if not r]
        for i, j in q:
            for I, J in (i+1, j), (i-1, j), (i, j+1), (i, j-1):
                if 0 <= I < len(rooms) and 0 <= J < len(rooms[0]) and rooms[I][J] > 2**30:
                    rooms[I][J] = rooms[i][j] + 1
                    q += (I, J),

  • 1
    S

    As good as it gets, as always :-).


  • 0
    F

    I always enjoy reading your code:-)


  • 0
    D

    your code is awesome!!!! I didn't know python can be written like you did.


  • 0

    Hey Stefan, I've learning your code for a long time. Your solution is concise and efficient. Here I post a DFS solution based on your format. Although it is not that efficient as BFS.

    class Solution(object):
        def wallsAndGates(self, rooms):
            s = [(i, j, 0) for i, row in enumerate(rooms) for j, r in enumerate(row) if not r]
            while s:
                i, j, step = s.pop()
                rooms[i][j] = step if rooms[i][j] > step else rooms[i][j]
                for I, J in ((i+1, j),(i-1, j),(i, j+1),(i, j-1)):
                    if 0 <= I < len(rooms) and 0 <= J < len(rooms[0]) and rooms[I][J] > step:
                        s += (I, J, step + 1),
    

  • 0
    S

    @StefanPochmann Can you please explain why your algorithm doesn't need to care about get the min value of the paths?

    For example:

    0    -1    -1  -1
    INF INF   [INF]  -1
    -1  -1    INF   0
    

    Your algorithm will set [INF] to be 3 since it starts from top left 0. However, the correct answer is 2 from bottom right.

    I think you need to check rooms[I][J] = min(rooms[i][j] + 1, rooms[I][J])

    Please elaborate. Thanks.


  • 0

    @hamster You should probably actually run my code on your input to avoid claiming that it does something which it really doesn't :-)


  • 0
    S

    @StefanPochmann Got it. My bad. Thanks.


  • 0
    S

    @StefanPochmann Unbelievable solution... can I ask how long it took you to come to this solution? 10 min? 1 hour?


  • 1

    @Samuri The code works because "for i, j in q" reads q from head to tail, just like a queue and q is dynamic in Python. In the first loop, INF(1,0) is set to 1 and then INF(2,2) is set to 1, too. In the second loop, INF(1,1) and INF(1,2) are set to 2, 0 and 1 in beginning and first loop are not considered any more. "for i, j in q" acts like BFS, not DFS.


  • 0
    Z

    Normally I hate to modify the list while for loop is iterating, but really I like this one, it is so cool. do you think replace the outer for loop by deque would make this algorithm more efficient or not?


  • 0
    Y
    This post is deleted!

  • 1
    Z

    @yixuanwang.start Nice video, I think the guy was talking about dict, there are some major difference,
    It is not safe to modify the dict key/value while iterating it (we cannot change the dict size, but we can modify it), because we have no idea where we are during iteration. but it is safe to append stuff to a list while iterating it and at least we can guarantee the correctness of the solution.


  • 0
    D

    @StefanPochmann

    Great idea and great code!
    I think BFS (queue) decided no need to check "rooms[I][J] = min(rooms[i][j] + 1, rooms[I][J])"!


Log in to reply
 

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