Python A* based Solution but TLE


  • 0
    L

    I think I have an A* based implementation to find path but I still get TLE. Would appreciate any help.

        def heuristic(self, start, end):
            return abs(end[0]-start[0]) + abs(end[1]-start[1])
        
        def neighbors(self, forest, x,y):
            nbrs = []
            arr = [(1,0),(-1,0),(0,1),(0,-1)]
            for a in arr:
                xx=a[0]+x
                yy=a[1]+y
                if 0<=xx<len(forest) and 0<=yy<len(forest[0]):
                    if forest[xx][yy]!=0: 
                        nbrs.append((xx,yy))
            return nbrs
         
        def get_distance(self, forest, start, end):
            distance = 0
            cost_so_far = {}
            came_from = {}
            cost_so_far[start]=0
            came_from[start]=None
            lpq = [(0, start)]; #heapq.heapify(lpq);
            
            while lpq:
                dist, node = heapq.heappop(lpq)
                if node == end:
                    break
                nbrs = self.neighbors(forest, node[0], node[1])
                for nbr in nbrs:
                    if forest[nbr[0]][nbr[1]]!=0:
                        nbr_cost = cost_so_far[node]+1 
                        if nbr not in cost_so_far or nbr_cost<cost_so_far[nbr]:
                            cost_so_far[nbr]=nbr_cost
                            priority = nbr_cost+self.heuristic(nbr, end)#f=g+h 
                            heapq.heappush(lpq, (priority, nbr))
                            came_from[nbr]=node # Store reverse path.
            node = end
            while node!=start:
                if node not in came_from: return -1
                node = came_from[node]
                distance+=1
            return distance
        def cutOffTree(self, forest):
            """
            :type forest: List[List[int]]
            :rtype: int
            """
            """
            Approach.
            #1- Put heights(>1) with matrix positions in a min. heap.(Height, (i,j))
            #2- For each pop() of the heap. Find the shorted_path from current node to the popped element.
            #3- While counting the steps for each traversal. Add the counts to total steps.
            """
            if not forest:
                return 0
            pq = []
            # Step 1
            for i in range(0, len(forest)):
                for j in range(0, len(forest[0])):
                    if forest[i][j]>1: 
                        heapq.heappush(pq, (forest[i][j], i, j))
            total_dist = 0
            start = (0,0)
            # Step 2
            while pq:
                ht, x, y = heapq.heappop(pq)         
                dist = self.get_distance(forest, start, (x, y))
                if dist==-1: return -1
                total_dist += dist
                start = (x,y)
                
            return total_dist
    

Log in to reply
 

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