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)): 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) 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)) seen.add((xn,yn)) return False def find_steps_bfs(self, forest, start, dest): dq = deque() dq.append((start, start)) seen = set() steps = 0 while dq: found = self.process_level(forest, dq, seen, dest, dest) 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