My multi-ended BFS solution with complex numbers


  • 1

    Clearly not the best solution around, but wanted to show some usage of complex numbers in Python and multi-ended BFS.

    class Solution(object):
        def shortestDistance(self, grid):
            grid = {r + c*1j: v 
                    for r, row in enumerate(grid) 
                    for c, v in enumerate(row)
                    if v != 2}
            levels = [[point] for point in grid if grid[point] == 1]
            distcs, hits = [{} for level in levels], {point: 0 for point in grid}
            n, shortest = len(levels), None
            counts, new_level, dead = [0] * n, [], 0
            
            for i, level in enumerate(levels):
                counts[i % n] += 1
                for point in level:
                    for neigh in {1, -1, 1j, -1j}:
                        addp = point + neigh
                        if addp in grid and grid[addp] != 1 and addp not in distcs[i % n]:
                            new_level.append(addp)
                            distcs[i % n][addp] = counts[i % n]
                            hits[addp] += 1
                if dead == n: break
                if not new_level: dead += 1
                levels += new_level,
                new_level = []
                
            return min([sum(distcs[i][point] 
                            for i in range(n)) 
                            for point in grid 
                            if hits[point] == n] 
                            or [-1])
    
            # 72 / 72 test cases passed.
    	# Status: Accepted
            # Runtime: 304 ms
    

Log in to reply
 

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