A-Star Search Algorithm in Python 3, (Faster than 90% solutions)
1) Sort the trees by height.\n2) Sum up the distance between successive trees. I have used A star search algorithm to find the distance between two trees.\n\nWh
1) Sort the trees by height.\n2) Sum up the distance between successive trees. I have used A star search algorithm to find the distance between two trees.\n\n**Why Astar?**\nWith BFS you circularly expand the explored area. With DFS, you pick a specific direction and explore in that direction until you reach the end, and then repeat the process. In Astar however, you move in the direction of the destination. The choice of the direction is based on two things. The distance g(n) from the source to current node, and h(n) a heuristic distance between current node and destination. Heuristic is a rough estimate, which can lead to a better solution. Here manhattan distance is used as the heuristic. \n\nMathematically, f(n) = g(n) + h(n)\n\nUse a priority queue (heap) to keep track of neighbouring nodes with smallest f(n) value and explore in that direction.\n\n```\nclass Solution:\n    def cutOffTree(self, forest: List[List[int]]) -> int:\n        m,n = len(forest), len(forest[0])\n        tree_order = []\n        for i in range(m):\n            for j in range(n):\n                if(forest[i][j] > 1):\n                    tree_order.append((forest[i][j],(i,j)))  # (tree height, cordinates)\n        tree_order.sort()\n        \n        def manhattan(s,t):\n            return abs(s[0] - t[0]) + abs(s[1] - t[1])\n        \n        def astar_search_distance(source, target):\n            pq  = [(manhattan(source, target), 0, source)] # Tuple content: (f= g+h, g, cordinates)\n            seen = set()\n            while(pq):\n                f,d,cur = heapq.heappop(pq)\n                if(cur == target):\n                    return d\n                i,j = cur\n                # Using for loop here will make the code cleaner, but will have extra boundary checks.\n                # Adding the cords into seen node while offering to pq, is much faster than adding after polling.\n                if(j+1<n and (i,j+1) not in seen and forest[i][j+1]!= 0): \n                    heapq.heappush(pq, (manhattan((i,j+1),target)+d+1, d+1, (i,j+1)))\n                    seen.add((i,j+1))\n                if(i+1<m and (i+1,j) not in seen and forest[i+1][j]!= 0): \n                    heapq.heappush(pq, (manhattan((i+1,j),target)+d+1, d+1, (i+1,j)))\n                    seen.add((i+1,j))\n                if(j-1>=0 and (i,j-1) not in seen and forest[i][j-1]!= 0): \n                    heapq.heappush(pq, (manhattan((i,j-1),target)+d+1, d+1, (i,j-1)))\n                    seen.add((i,j-1))\n                if(i-1>=0 and (i-1,j) not in seen and forest[i-1][j]!= 0): \n                    heapq.heappush(pq, (manhattan((i-1,j),target)+d+1, d+1, (i-1,j)))\n                    seen.add((i-1,j))\n                    \n            return -1\n\t\t\t\n        prev = (0,0)\n        res = 0\n        for tree in tree_order:\n            d = astar_search_distance(prev, tree[1])\n            if(d == -1): break\n            res += d\n            prev = tree[1]\n            \n        return res if d != -1 else -1\n```
[]