Python A* based Solution but TLE

• 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)