python BFS solution


  • 3
    Z

    Here used some tricks learned from @StefanPochmann

    class Solution(object):
        def updateMatrix(self, matrix):
            q, m, n = [], len(matrix), len(matrix[0])
            for i in xrange(m):
                for j in xrange(n):
                    if matrix[i][j] != 0:
                        matrix[i][j] = 0x7fffffff
                    else:
                        q.append((i, j))
            for i, j in q:
                for r, c in ((i, 1+j), (i, j-1), (i+1, j), (i-1, j)):
                    z = matrix[i][j] + 1
                    if 0 <= r < m and 0 <= c < n and matrix[r][c] > z:
                        matrix[r][c] = z
                        q.append((r, c))
            return matrix

  • 0

    I've never seen r not in (-1, m), I think 0 <= r < m is much better.


  • 0
    Z

    @StefanPochmann Yeah, I was doing something like this, but forgot to rewrite the code. Thanks for the reminder.

    if r in (-1, m) or c in (-1, n):
        continue
    

  • 1
    A

    @zhongyuan9817 said in python BFS solution:

    what is going on here?

    for i, j in q:
    for r, c in ((i, 1+j), (i, j-1), (i+1, j), (i-1, j)):
    z = matrix[i][j] + 1
    if 0 <= r < m and 0 <= c < n and matrix[r][c] > z:
    matrix[r][c] = z
    q.append((r, c))
    return matrix

    especially here:
    matrix[r][c] > z


Log in to reply
 

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