Python, normal and priority BFS, faster than 99% and faster than 77%
normal bfs\n\n\n\nclass Solution:\n    def cutOffTree(self, forest: List[List[int]]) -> int:\n        forest.append([0] * len(forest[0]))\n        for row in fo
## normal bfs\n![image](https://assets.leetcode.com/users/images/f70bca63-7c1d-4a5d-9b9b-d2a5ac4733e7_1620800536.5729027.png)\n\n```\nclass Solution:\n    def cutOffTree(self, forest: List[List[int]]) -> int:\n        forest.append([0] * len(forest[0]))\n        for row in forest: row.append(0)\n        def bfs(end, start):\n            if end == start: return 0\n            visited, queue = set(), {start}\n            visited.add(start)\n            step = 0\n            while queue:\n                s = set()\n                step += 1\n                for p in queue:                    \n                    for dr, dc in ((-1, 0), (1, 0), (0, 1), (0, -1)):\n                        r, c = p[0] + dr, p[1] + dc\n                        if not forest[r][c] or (r, c) in visited: continue\n                        if (r, c) == end: return step\n                        visited.add((r, c))\n                        s.add((r, c))\n                queue = s\n\n        trees = [(height, r, c) for r, row in enumerate(forest) for c, height in enumerate(row) if forest[r][c] > 1]\n        # check\n        queue = [(0, 0)]\n        reached = set()\n        reached.add((0, 0))\n        while queue:\n            r, c = queue.pop()\n            for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):\n                row, col = r + dr, c + dc\n                if forest[row][col] and (row, col) not in reached:\n                    queue.append((row, col))\n                    reached.add((row,col))\n        if not all([(i, j) in reached for (height, i, j) in trees]): return -1\n        trees.sort()\n        return sum([bfs((I,J),(i,j)) for (_, i, j), (_, I, J) in zip([(0, 0, 0)] + trees, trees)])\n```\n## priority bfs\n![image](https://assets.leetcode.com/users/images/87009e0b-3b8f-4ad1-96db-f3582810ef95_1620800616.6076303.png)\n\n```\nclass Solution:\n    def cutOffTree(self, forest: List[List[int]]) -> int:\n        forest.append([0] * len(forest[0]))\n        for row in forest: row.append(0)\n        # distance\n        def distance(i, j, I, J):\n            manhattan = abs(i - I) + abs(j - J)\n            detour = 0\n            good, bad = [(i, j)], []\n            visited = set()\n            while True:\n                if not good:\n                    good, bad = bad, []\n                    detour += 1\n                i, j = good.pop()\n                if i == I and j == J: return manhattan + detour * 2\n                if (i, j) in visited: continue\n                visited.add((i, j))\n                for i, j, closer in ((i-1, j, i > I), (i+1, j, i < I), (i, j+1, j < J), (i, j-1, j > J)):\n                    if forest[i][j]:\n                        (good if closer else bad).append((i, j))\n                    \n        trees = [(height, r, c) for r, row in enumerate(forest) for c, height in enumerate(row) if forest[r][c] > 1]\n        # check\n        queue = [(0, 0)]\n        reached = set()\n        reached.add((0, 0))\n        while queue:\n            r, c = queue.pop()\n            for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):\n                row, col = r + dr, c + dc\n                if forest[row][col] and (row, col) not in reached:\n                    queue.append((row, col))\n                    reached.add((row,col))\n        if not all([(i, j) in reached for (height, i, j) in trees]): return -1\n        trees.sort()\n        return sum([distance(i, j, I, J) for (_, i, j), (_, I, J) in zip([(0, 0, 0)] + trees, trees)])\n```
['Breadth-First Search', 'Python', 'Python3']