Python solution with detailed explanation


  • 1
    G

    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))
                        seen.add((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    
    

  • 0
    A

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


Log in to reply
 

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