Problem statement

https://leetcode.com/problems/cut-off-trees-for-golf-event/

Solution 1

Here we need to have a function to find shortest distance from one point to another. Then we just apply this function a lot of times for trees in ascending order.

Complexity

Time complexity is O(mnT) <= O(m^2n^2), where T is number of trees; space complexity is O(mn).

Code

class Solution:
    def cutOffTree(self, forest):
        m, n = len(forest), len(forest[0])
        trees = [(forest[i][j], i, j) for i in range(m) for j in range(n) if forest[i][j] > 1]
        trees.sort()
        trees = [(0,0,0)] + trees
        out = 0
        neibs = [[-1,0],[1,0],[0,1],[0,-1]]
        
        def bfs(sx, sy, ex, ey, k):
            queue = deque([(sx, sy, 0)])
            while queue:
                x, y, d = queue.popleft()
                if (x, y) == (ex, ey): return d
                for dx, dy in neibs:
                    if 0 <= x+dx < m and 0 <= y+dy < n and forest[x+dx][y+dy] not in [0, k]: 
                        queue.append((x+dx, y+dy, d+1))
                        forest[x+dx][y+dy] = k
            return -1
        
        for i in range(len(trees) - 1):
            path = bfs(trees[i][1],trees[i][2],trees[i+1][1],trees[i+1][2],-i-1)
            if path == -1: return -1
            else: out += path
        
        return out

Solution 2

There is also Hadlock’s Algorithm with the same worse complexity which work in practice much faster. The idea is to first consider cells which are closer to our target: so put them to the left of our deque and if we have some detours, we put them to the right of our deque.

Complexity

Code

class Solution:
    def cutOffTree(self, forest):
        m, n = len(forest), len(forest[0])
        trees = [(forest[i][j], i, j) for i in range(m) for j in range(n) if forest[i][j] > 1]
        trees.sort()
        trees = [(0,0,0)] + trees
        out = 0
        neibs = [[-1,0],[1,0],[0,1],[0,-1]]
        
        def bfs(sx, sy, ex, ey, k):
            queue = deque([(sx, sy, 0)])
            while queue:       
                x, y, d = queue.popleft()
                forest[x][y] = k
                if (x, y) == (ex, ey): return abs(sx-ex) + abs(sy-ey) + 2*d
                for xn, yn, closer in ((x-1,y,x>ex),(x+1,y,x<ex),(x,y-1,y>ey),(x,y+1,y<ey)):
                    if 0 <= xn < m and 0 <= yn < n and forest[xn][yn] not in [0, k]:
                        if closer:
                            queue.appendleft((xn, yn, d))
                        else:
                            queue.append((xn, yn, d+1))
            return -1
        
        for i in range(len(trees) - 1):
            path = bfs(trees[i][1],trees[i][2],trees[i+1][1],trees[i+1][2],-i-1)
            if path == -1: return -1
            else: out += path
        
        return out