Python 3 || improving BFS to avoid TLE
Intuition\n Describe your first thoughts on how to solve this problem. \nBasically we sort the tree heights and get a sequence $(p_0,p_1,\ldots, p_k)$ of tree p
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nBasically we sort the tree heights and get a sequence $(p_0,p_1,\\ldots, p_k)$ of tree position, where $p_0=(0,0)$ is the starting position. Then, similar to most of the approaches, BFS is empolyed to find the distance between $p_i$ and $p_{i+1}$ for each $i$. However, this approach will suffer from TLE for Python coder.  \n# Approach\n<!-- Describe your approach to solving the problem. -->\nWe suggest a very simpe improvement for BFS. We can find the distance from one source to two destinations in one BFS. That is, we find the $distance(p_i, p_{i-1}) + distance(p_i, p_{i+1})$ in one BFS procedure. The number of BFS will be cut in half. \n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$O(mnk)$, where $k$ is the number of trees. The complexity in Big-O is the same, but running time is one half.\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$O(mn)$, the same.\n# Code\n```\nclass Solution:\n    # BFS search from i to i-1 and i+1\n    def cutOffTree(self, forest: List[List[int]]) -> int:\n        forest = [[0]*len(forest[0])] + forest \n        # sentinel to save index check\n        forest.append([0]*len(forest[0]))\n        for i in range(len(forest)):\n            forest[i] = [0]+forest[i]+[0]\n        seq = [(0,1,1)] # starting point\n        D0 = dict()\n        for i,row in enumerate(forest):\n            for j,x in enumerate(row):\n                if x>1: seq.append((x,i,j))\n                elif x==0: D0[(i,j)]=-1\n        seq.sort() # sort the tree height\n        def bfs(p0,p1,p2): # distance (p0,p1)+(p0,p2)\n            #print(p0,p1,p2)\n            que=[p0]; head=0 # FIFO queue\n            D = D0.copy() # all 0 visited\n            D[p0] = 0\n            while head<len(que) and (p1 not in D or p2 not in D):\n                r,c = que[head]; head += 1\n                nd = D[(r,c)]+1\n                for nr,nc in ((r-1,c),(r+1,c),(r,c-1),(r,c+1)):\n                    if (nr,nc) not in D:\n                        D[(nr,nc)] = nd\n                        que.append((nr,nc))\n                #end for\n            #endwhile\n            if p1 not in D or p2 not in D:\n                return -1\n            return D[p1]+D[p2]\n        #end BFS\n        total = 0\n        while len(seq)>2:\n            # find dustance for last 3 points\n            step = bfs(seq[-2][1:],seq[-1][1:],seq[-3][1:])\n            if step<0: return -1\n            total += step\n            seq.pop(); seq.pop()\n        if len(seq)>1: # when only two points left\n            step = bfs(seq[0][1:],seq[0][1:],seq[1][1:])\n            if step<0: return -1\n            total += step\n        return total\n\n\n```
['Python3']