SPFA algorithm, python


  • 0
    W
    class Solution(object):
        def wallsAndGates(self, rooms):
            n = len(rooms)
            if n == 0:
                return
            m = len(rooms[0])
            q = []
            vis = [[False for j in xrange(m)] for i in xrange(n)]
            for i in xrange(n):
                for j in xrange(m):
                    if rooms[i][j] == 0:
                        vis[i][j] = True
                        q.append((i,j,0))
            
            while q:
                cache = []
                for node in q:
                    i, j, dis = node
                    vis[i][j] = False
                    for dir in [(-1,0), (1,0), (0,1),(0,-1)]:
                        x = i + dir[0]
                        y = j + dir[1]
                        if 0 <= x < n and 0 <= y < m and dis + 1 < rooms[x][y]:
                            rooms[x][y] = dis + 1
                            if not vis[x][y]:
                                vis[x][y] = True
                                cache.append((x, y, rooms[x][y]))
                q = cache

Log in to reply
 

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