## 675. Cut Off Trees for Golf Event

You are asked to cut off trees in a forest for a golf event. The forest is represented as a non-negative 2D map, in this map:

1. `0` represents the `obstacle` can't be reached.
2. `1` represents the `ground` can be walked through.
3. `The place with number bigger than 1` represents a `tree` can be walked through, and this positive number represents the tree's height.

You are asked to cut off all the trees in this forest in the order of tree's height - always cut off the tree with lowest height first. And after cutting, the original place has the tree will become a grass (value 1).

You will start from the point (0, 0) and you should output the minimum steps you need to walk to cut off all the trees. If you can't cut off all the trees, output -1 in that situation.

You are guaranteed that no two `trees` have the same height and there is at least one tree needs to be cut off.

Example 1:

```Input:
[
[1,2,3],
[0,0,4],
[7,6,5]
]
Output: 6
```

Example 2:

```Input:
[
[1,2,3],
[0,0,0],
[7,6,5]
]
Output: -1
```

Example 3:

```Input:
[
[2,3,4],
[0,0,5],
[8,7,6]
]
Output: 6
Explanation: You started from the point (0,0) and you can cut off the tree in (0,0) directly without walking.
```

Hint: size of the given matrix will not exceed 50x50.

b'
\n\n

#### Approach Framework

\n

Explanation

\n

Starting from `(0, 0)`, for each tree in height order, we will calculate the distance from where we are to the next tree (and move there), adding that distance to the answer.

\n

We frame the problem as providing some distance function `dist(forest, sr, sc, tr, tc)` that calculates the path distance from source `(sr, sc)` to target `(tr, tc)` through obstacles `dist[i][j] == 0`. (This distance function will return `-1` if the path is impossible.)

\n

What follows is code and complexity analysis that is common to all three approaches. After, the algorithms presented in our approaches will focus on only providing our `dist` function.

\n

Python

\n
`class Solution(object):\n    def cutOffTree(self, forest):\n        trees = sorted((v, r, c) for r, row in enumerate(forest)\n                       for c, v in enumerate(row) if v > 1)\n        sr = sc = ans = 0\n        for _, tr, tc in trees:\n            d = dist(forest, sr, sc, tr, tc)\n            if d < 0: return -1\n            ans += d\n            sr, sc = tr, tc\n        return ans\n`
\n

Java

\n
`class Solution {\n    int[] dr = {-1, 1, 0, 0};\n    int[] dc = {0, 0, -1, 1};\n\n    public int cutOffTree(List<List<Integer>> forest) {\n        List<int[]> trees = new ArrayList();\n        for (int r = 0; r < forest.size(); ++r) {\n            for (int c = 0; c < forest.get(0).size(); ++c) {\n                int v = forest.get(r).get(c);\n                if (v > 1) trees.add(new int[]{v, r, c});\n            }\n        }\n\n        Collections.sort(trees, (a, b) -> Integer.compare(a, b));\n\n        int ans = 0, sr = 0, sc = 0;\n        for (int[] tree: trees) {\n            int d = dist(forest, sr, sc, tree, tree);\n            if (d < 0) return -1;\n            ans += d;\n            sr = tree; sc = tree;\n        }\n        return ans;\n    }\n}\n`
\n

Complexity Analysis

\n

All three algorithms have similar worst case complexities, but in practice each successive algorithm presented performs faster on random data.

\n
\n
• \n

Time Complexity: where there are rows and columns in the given `forest`. We walk to trees, and each walk could spend time searching for the tree.

\n
• \n
• \n

Space Complexity: , the maximum size of the data structures used.

\n
• \n
\n
\n

#### Approach #1: BFS [Accepted]

\n

Intuition and Algorithm

\n

We perform a breadth-first-search, processing nodes (grid positions) in a queue. `seen` keeps track of nodes that have already been added to the queue at some point - those nodes will be already processed or are in the queue awaiting processing.

\n

For each node that is next to be processed, we look at it\'s neighbors. If they are in the forest (grid), they haven\'t been enqueued, and they aren\'t an obstacle, we will enqueue that neighbor.

\n

We also keep a side count of the distance travelled for each node. If the node we are processing is our destination \'target\' `(tr, tc)`, we\'ll return the answer.

\n

Python

\n
`def bfs(forest, sr, sc, tr, tc):\n    R, C = len(forest), len(forest)\n    queue = collections.deque([(sr, sc, 0)])\n    seen = {(sr, sc)}\n    while queue:\n        r, c, d = queue.popleft()\n        if r == tr and c == tc:\n            return d\n        for nr, nc in ((r-1, c), (r+1, c), (r, c-1), (r, c+1)):\n            if (0 <= nr < R and 0 <= nc < C and\n                    (nr, nc) not in seen and forest[nr][nc]):\n                seen.add((nr, nc))\n                queue.append((nr, nc, d+1))\n    return -1\n`
\n

Java

\n
`public int bfs(List<List<Integer>> forest, int sr, int sc, int tr, int tc) {\n    int R = forest.size(), C = forest.get(0).size();\n    Queue<int[]> queue = new LinkedList();\n    queue.add(new int[]{sr, sc, 0});\n    boolean[][] seen = new boolean[R][C];\n    seen[sr][sc] = true;\n    while (!queue.isEmpty()) {\n        int[] cur = queue.poll();\n        if (cur == tr && cur == tc) return cur;\n        for (int di = 0; di < 4; ++di) {\n            int r = cur + dr[di];\n            int c = cur + dc[di];\n            if (0 <= r && r < R && 0 <= c && c < C &&\n                    !seen[r][c] && forest.get(r).get(c) > 0) {\n                seen[r][c] = true;\n                queue.add(new int[]{r, c, cur+1});\n            }\n        }\n    }\n    return -1;\n}\n`
\n
\n

#### Approach #2: A* Search [Accepted]

\n

Intuition and Algorithm

\n

The A star algorithm is another path-finding algorithm. For every node at position `(r, c)`, we have some estimated cost `node.f = node.g + node.h`, where `node.g` is the actual distance from `(sr, sc)` to `(r, c)`, and `node.h` is our heuristic* (guess) of the distance from `(r, c)` to `(tr, tc)`. In this case, our guess will be the taxicab distance, `node.h = abs(r-tr) + abs(c-tc)`.

\n

We keep a priority queue to decide what node to search in (expand) next. We can prove that if we find the target node, we must have travelled the lowest possible distance `node.g`. By considering the last time where two backwards paths are the same, without loss of generality we could suppose the the penultimate square of the two paths are different, and then in this case `node.f = node.g + 1`, showing the path with less actual distance travelled is expanded first as desired.

\n

It might be useful for solvers familiar with Dijkstra\'s Algorithm to know that A* Search is a special case of Dijkstra\'s with `node.h = 0` always.

\n

Python

\n
`def astar(forest, sr, sc, tr, tc):\n    R, C = len(forest), len(forest)\n    heap = [(0, 0, sr, sc)]\n    cost = {(sr, sc): 0}\n    while heap:\n        f, g, r, c = heapq.heappop(heap)\n        if r == tr and c == tc: return g\n        for nr, nc in ((r-1,c), (r+1,c), (r,c-1), (r,c+1)):\n            if 0 <= nr < R and 0 <= nc < C and forest[nr][nc]:\n                ncost = g + 1 + abs(nr - tr) + abs(nc - tc)\n                if ncost < cost.get((nr, nc), 9999):\n                    cost[nr, nc] = ncost\n                    heapq.heappush(heap, (ncost, g+1, nr, nc))\n    return -1\n`
\n

Java

\n
`public int cutOffTree(List<List<Integer>> forest, int sr, int sc, int tr, int tc) {\n    int R = forest.size(), C = forest.get(0).size();\n    PriorityQueue<int[]> heap = new PriorityQueue<int[]>(\n        (a, b) -> Integer.compare(a, b));\n    heap.offer(new int[]{0, 0, sr, sc});\n\n    HashMap<Integer, Integer> cost = new HashMap();\n    cost.put(sr * C + sc, 0);\n\n    while (!heap.isEmpty()) {\n        int[] cur = heap.poll();\n        int g = cur, r = cur, c = cur;\n        if (r == tr && c == tc) return g;\n        for (int di = 0; di < 4; ++di) {\n            int nr = r + dr[di], nc = c + dc[di];\n            if (0 <= nr && nr < R && 0 <= nc && nc < C && forest.get(nr).get(nc) > 0) {\n                int ncost = g + 1 + Math.abs(nr-tr) + Math.abs(nc-tr);\n                if (ncost < cost.getOrDefault(nr * C + nc, 9999)) {\n                    cost.put(nr * C + nc, ncost);\n                    heap.offer(new int[]{ncost, g+1, nr, nc});\n                }\n            }\n        }\n    }\n    return -1;\n}\n`
\n
\n

#### Approach #3: Hadlock\'s Algorithm [Accepted]

\n

Intuition

\n

Without any obstacles, the distance from `source = (sr, sc)` to `target = (tr, tc)` is simply `taxi(source, target) = abs(sr-tr) + abs(sc-tc)`. This represents a sort of minimum distance that must be travelled. Whenever we walk "away" from the target, we increase this minimum by 2, as we stepped 1 move, plus the taxicab distance from our new location has increased by one.

\n

Let\'s call such a move that walks away from the target a detour. It can be proven that the distance from source to target is simply `taxi(source, target) + 2 * detours`, where `detours` is the smallest number of detours in any path from `source` to `target`.

\n

Algorithm

\n

With respect to a `source` and `target`, call the detour number of a square to be the lowest number of detours possible in any path from `source` to that square. (Here, detours are defined with respect to `target` - the number of away steps from that target.)

\n

We will perform a priority-first-search in order of detour number. If the target is found, it was found with the lowest detour number and therefore the lowest corresponding distance. This motivates using `processed`, keeping track of when nodes are expanded, not visited - nodes could potentially be visited twice.

\n

As each neighboring node can only have the same detour number or a detour number one higher, we will only consider at most 2 priority classes at a time. Thus, we can use a deque (double ended queue) to perform this implementation. We will place nodes with the same detour number to be expanded first, and nodes with a detour number one higher to be expanded after all nodes with the current number are done.

\n

Python

\n
`def hadlocks(forest, sr, sc, tr, tc):\n    R, C = len(forest), len(forest)\n    processed = set()\n    deque = collections.deque([(0, sr, sc)])\n    while deque:\n        detours, r, c = deque.popleft()\n        if (r, c) not in processed:\n            processed.add((r, c))\n            if r == tr and c == tc:\n                return abs(sr-tr) + abs(sc-tc) + 2*detours\n            for nr, nc, closer in ((r-1, c, r > tr), (r+1, c, r < tr),\n                                   (r, c-1, c > tc), (r, c+1, c < tc)):\n                if 0 <= nr < R and 0 <= nc < C and forest[nr][nc]:\n                    if closer:\n                        deque.appendleft((detours, nr, nc))\n                    else:\n                        deque.append((detours+1, nr, nc))\n    return -1\n`
\n

Java

\n
`public int hadlocks(List<List<Integer>> forest, int sr, int sc, int tr, int tc) {\n    int R = forest.size(), C = forest.get(0).size();\n    Set<Integer> processed = new HashSet();\n    Deque<int[]> deque = new ArrayDeque();\n    deque.offerFirst(new int[]{0, sr, sc});\n    while (!deque.isEmpty()) {\n        int[] cur = deque.pollFirst();\n        int detours = cur, r = cur, c = cur;\n        if (!processed.contains(r*C + c)) {\n            processed.add(r*C + c);\n            if (r == tr && c == tc) {\n                return Math.abs(sr-tr) + Math.abs(sc-tc) + 2 * detours;\n            }\n            for (int di = 0; di < 4; ++di) {\n                int nr = r + dr[di];\n                int nc = c + dc[di];\n                boolean closer;\n                if (di <= 1) closer = di == 0 ? r > tr : r < tr;\n                else closer = di == 2 ? c > tc : c < tc;\n                if (0 <= nr && nr < R && 0 <= nc && nc < C && forest.get(nr).get(nc) > 0) {\n                    if (closer) deque.offerFirst(new int[]{detours, nr, nc});\n                    else deque.offerLast(new int[]{detours+1, nr, nc});\n                }\n            }\n        }\n    }\n    return -1;\n}\n`
\n
\n

Analysis written by: @awice.

\n
'