# Python solution with detailed explanation

• Cut Off Trees for Golf Event https://leetcode.com/problems/cut-off-trees-for-golf-event/description/

BFS based solution (in Python gives TLE)

• Use a priority queue to arrange all trees in ascending height order.
• Then simply use BFS to find the minimum steps between consecutive trees.
• Time complexity: O(m^2 * n^2)
``````from heapq import heappop, heappush
from collections import deque

class Solution:
def build_pq(self, forest):
pq = []
for i in range(len(forest)):
for j in range(len(forest[0])):
if forest[i][j] > 1:
heappush(pq, (forest[i][j], i, j))
return pq

def process_level(self, forest, dq, seen, xdest, ydest):
M,N = len(forest), len(forest[0])
for _ in range(len(dq)):
x2, y2 = dq.popleft()
if x2 == xdest and y2 == ydest:
return True
for xn,yn in ((x2-1,y2),(x2+1,y2),(x2,y2-1),(x2,y2+1)):
if 0<=xn<M and 0<=yn<N and forest[xn][yn] != 0 and (xn,yn) not in seen:
dq.append((xn,yn))
return False

def find_steps_bfs(self, forest, start, dest):
dq = deque()
dq.append((start[0], start[1]))
seen = set()
steps = 0
while dq:
found = self.process_level(forest, dq, seen, dest[0], dest[1])
if found:
break
else:
steps += 1
return steps if found else -1

def cutOffTree(self, forest):
"""
:type forest: List[List[int]]
:rtype: int
"""
pq = self.build_pq(forest)
xstart, ystart, steps = 0, 0, 0
while pq:
ht, xdest, ydest = heappop(pq)
curr_step = self.find_steps_bfs(forest, (xstart, ystart), (xdest, ydest))
if curr_step == -1:
return -1
else:
steps += curr_step
xstart, ystart = xdest, ydest
return steps
``````

• I re-submit your code, it's TLE....

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