675. Cut Off Trees for Golf Event - cocoder39/coco39_LC GitHub Wiki

675. Cut Off Trees for Golf Event

T = O (M * N * T) where T is number of trees

class Solution:
    def cutOffTree(self, forest: List[List[int]]) -> int:
        m, n = len(forest), len(forest[0])
        trees = []
        for i in range(m):
            for j in range(n):
                if forest[i][j] > 1:
                    trees.append((forest[i][j], i, j))
        trees.sort()
        
        res = 0
        startX, startY = 0, 0
        for _, targetX, targetY in trees:
            dist = self.getDist(forest, startX, startY, targetX, targetY)
            if dist == -1:
                return -1
            res += dist
            startX, startY = targetX, targetY
        return res
    
    def getDist(self, forest: int, startX: int, startY: int, targetX: int, targetY: int) -> int:
        if startX == targetX and startY == targetY:
            return 0
        
        DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        
        m, n = len(forest), len(forest[0])
        visited = [[False] * n for _ in range(m)]
        
        queue = collections.deque()
        queue.append([startX, startY, 0])
        visited[startX][startY] = True
        while queue:
            x, y, dist = queue.popleft()
            for dx, dy in DIRS:
                nx, ny = x + dx, y + dy
                if 0 <= nx < m and 0 <= ny < n and forest[nx][ny] and not visited[nx][ny]:
                    if nx == targetX and ny == targetY:
                        return dist+1
                    visited[nx][ny] = True
                    queue.append([nx, ny, dist+1])
        return -1