675: Solution with step by step explanation
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n1. We first initialize the size of the forest m and n. We also create an 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n1. We first initialize the size of the forest m and n. We also create an empty list called trees which will contain tuples of (height, x, y) where x and y are the coordinates of the tree in the forest.\n\n2. We iterate through every cell in the forest and if the value is greater than 1, we append a tuple of (height, x, y) to the trees list. We sort the list by the height of the trees in ascending order.\n\n3. We define a bfs function which takes in the starting coordinates sx and sy, and the target coordinates tx and ty. We use a heap to implement Dijkstra\'s algorithm for finding the shortest path. We keep track of the minimum distance d, current coordinates x and y, and push the tuple (d, x, y) into the heap.\n\n4. We create a visited set to keep track of cells that have been visited. We add the starting coordinates to the set.\n\n5. While the heap is not empty, we pop the cell with the minimum distance d from the heap. If the current coordinates are the target coordinates, we return the minimum distance d.\n\n6. Otherwise, we iterate through all possible directions (north, east, south, west) and check if the next cell is within the boundaries of the forest, not in the visited set, and not blocked by a tree. If the conditions are met, we add the next cell to the visited set and push the tuple (d+1, nx, ny) into the heap.\n\n7. If the target coordinates cannot be reached, we return -1.\n\n8. We initialize ans to 0, and the starting coordinates sx and sy to (0, 0).\n\n9. We iterate through every tree in the trees list in ascending order of height. For each tree,\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def cutOffTree(self, forest: List[List[int]]) -> int:\n        m, n = len(forest), len(forest[0])\n        trees = []\n        for i in range(m):\n            for j in range(n):\n                if forest[i][j] > 1:\n                    trees.append((forest[i][j], i, j))\n        trees.sort()\n\n        def bfs(sx, sy, tx, ty):\n            queue = [(0, sx, sy)]\n            visited = set()\n            visited.add((sx, sy))\n            while queue:\n                d, x, y = heapq.heappop(queue)\n                if x == tx and y == ty:\n                    return d\n                for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:\n                    nx, ny = x + dx, y + dy\n                    if 0 <= nx < m and 0 <= ny < n and (nx, ny) not in visited and forest[nx][ny]:\n                        visited.add((nx, ny))\n                        heapq.heappush(queue, (d+1, nx, ny))\n            return -1\n\n        ans = 0\n        sx, sy = 0, 0\n        for _, tx, ty in trees:\n            d = bfs(sx, sy, tx, ty)\n            if d == -1:\n                return -1\n            ans += d\n            sx, sy = tx, ty\n        return ans\n\n```
['Array', 'Breadth-First Search', 'Heap (Priority Queue)', 'Python', 'Python3']