[Python3] Priority queue + Bidirectional BFS
The problem is actually easy with this one intuition. Since, the trees have to be cut in increasing order of height and the heights are distinct, there is alway
The problem is actually easy with this one intuition. Since, the trees have to be cut in increasing order of height and the heights are distinct, there is always only one cell we need to visit next. The problem then becomes how fast can we get from the current cell to the next cell which is BFS! The problem reduces to performing X BFS calls where X is the number of trees.\n\nConsider the example\n```\n[5, 4, 6]\n[0, 0, 2]\n[10, 11, 12]\n```\n\nWe start at (0, 0) and the height is 5. But we cannot cut it yet as there is a tree with height 2 at (1, 2). So the first step is to get from (0, 0) to (1, 2). After getting to (1, 2) we cut the tree. The next shortest tree is at (0, 1) with  a height of 4. So now we need to move from (1, 2) to (0, 1).\n\nThe order of the trees to cut can be maintained using a min heap. If at any point, we are not able to reach the next tree, just return -1. A bidirectional BFS helps speed up the search.\n\nTime Complexity: O((MN)^2 * lgMN)\nM is the number of rows and N is the number of columns\nAll the cells could be in the heap and processing all of them takes MN lgMN\nEach BFS search could take a maximum of MN time\n\nSpace complexity: O(MN)\nThe heap takes O(MN) space. One run of BFS takes O(MN) space and it is discarded once complete.\n\n```\nimport heapq\n\nclass Solution:\n    def cutOffTree(self, forest: List[List[int]]) -> int:\n        def bfs(start, end):\n            if start == end:\n                return 0\n            \n            fwd, rev = [start], [end]\n            visited_fwd, visited_rev = set(fwd), set(rev)\n            steps = 0\n            while fwd:\n                if len(fwd) > len(rev):\n                    fwd, rev = rev, fwd\n                    visited_fwd, visited_rev = visited_rev, visited_fwd\n                \n                nxt = []\n                for i, k in fwd:\n                    for x, y in directions:\n                        nxt_i, nxt_k = i + x, k + y\n                        if 0 <= nxt_i < m and 0 <= nxt_k < n and forest[nxt_i][nxt_k] != 0 and (nxt_i, nxt_k) not in visited_fwd:\n                            if (nxt_i, nxt_k) in visited_rev:\n                                return steps + 1\n                            visited_fwd.add((nxt_i, nxt_k))\n                            nxt.append((nxt_i, nxt_k))\n                \n                steps += 1\n                fwd = nxt\n            \n            return -1\n        \n        m, n = len(forest), len(forest[0])\n        min_steps = 0\n        directions = ((0, 1), (0, -1), (1, 0), (-1, 0))\n        curr = (0, 0)\n        \n        heap = []\n        for i, k in product(range(m), range(n)):\n            if forest[i][k] > 1:\n                heapq.heappush(heap, (forest[i][k], (i, k)))\n        \n        while heap:\n            _, nxt = heapq.heappop(heap)\n            min_steps_to_nxt = bfs(curr, nxt)\n            if min_steps_to_nxt == -1:\n                return -1\n            \n            min_steps += min_steps_to_nxt\n            curr = nxt\n        \n        return min_steps\n```
[]