Cut Off Trees For Golf Event Problem


Description

LeetCode Problem 675.

You are asked to cut off all the trees in a forest for a golf event. The forest is represented as an m x n matrix. In this matrix:

  • 0 means the cell cannot be walked through.
  • 1 represents an empty cell that can be walked through.
  • A number greater than 1 represents a tree in a cell that can be walked through, and this number is the tree’s height.

In one step, you can walk in any of the four directions: north, east, south, and west. If you are standing in a cell with a tree, you can choose whether to cut it off.

You must cut off the trees in order from shortest to tallest. When you cut off a tree, the value at its cell becomes 1 (an empty cell).

Starting from the point (0, 0), return the minimum steps you need to walk to cut off all the trees. If you cannot cut off all the trees, return -1.

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:

1
2
3
Input: forest = [[1,2,3],[0,0,4],[7,6,5]]
Output: 6
Explanation: Following the path above allows you to cut off the trees from shortest to tallest in 6 steps.

Example 2:

1
2
3
Input: forest = [[1,2,3],[0,0,0],[7,6,5]]
Output: -1
Explanation: The trees in the bottom row cannot be accessed as the middle row is blocked.

Example 3:

1
2
3
4
Input: forest = [[2,3,4],[0,0,5],[8,7,6]]
Output: 6
Explanation: You can follow the same path as Example 1 to cut off all the trees.
Note that you can cut off the first tree at (0, 0) before making any steps.

Constraints:

  • m == forest.length
  • n == forest[i].length
  • 1 <= m, n <= 50
  • 0 <= forest[i][j] <= 10^9


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
class Solution {
public:
    int cutOffTree(vector<vector<int>>& forest) {
        int rows = forest.size();
        int cols = rows ? forest[0].size() : 0;
        
        if (!rows || !cols) {
            return 0;
        }
        // Start location is blocked
        if (forest[0][0] == 0) {
            return -1;
        }
        
        // Min queue of trees based on height
         priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> trees;
        
        for (int r = 0; r < rows; ++r) {
            for (int c = 0; c < cols; ++c) {
                if (forest[r][c] > 1) {
                   trees.push({forest[r][c], {r, c}}); 
                }
            }
        }
        
        // Legal moves
        vector<pair<int, int>> moves = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
        // Track visited
        vector<vector<int>> visited(rows, vector<int>(cols, -1));
        // Total distance
        int totalDist = 0;
        // Start location
        pair<int, int> start = {0, 0};
        // Tree ID
        int i = 0;
        
        // Iterate through trees in increasing height order
        while (!trees.empty()) {
            pair<int, int> to = trees.top().second;
            trees.pop();
            
            // Level order traversal
            bool found = false;
            int dist = -1;  
            queue<pair<int, int>> qu;
            
            qu.push({start.first, start.second});
            visited[start.first][start.second] = i;
            
            while (!qu.empty() && !found) {
                ++dist;
                
                for (int j = 0, r, c, size = qu.size(); j < size && !found; ++j) {
                    tie(r, c) = qu.front();
                    qu.pop();
                
                    // Break if target location found
                    if (r == to.first && c == to.second) {
                        found = true;
                        break;
                    }
                
                    for (int m = 0, nr, nc; m < 4; ++m) {
                        // New location
                        nr = r + moves[m].first;
                        nc = c + moves[m].second;

                        // Skip out of bound, blockages and already scheduled
                        if (nr < 0 || nr >= rows || nc < 0 || nc >= cols || visited[nr][nc] == i || forest[nr][nc] == 0) {
                            continue;
                        }
                            
                        // Mark visited asap otherwise it will be scheduled mutiple times
                        visited[nr][nc] = i;
                        qu.push({nr, nc});
                    }
                }
            }
            
            // Return if not found
            if (!found) {
                return -1;
            }
            
            // Update total distance
            totalDist += dist;
            // Update start
            start = to;
            // Update id
            ++i;
        }
        
        return totalDist;
    }
};




Related Posts

Snakes And Ladders Problem

LeetCode 909. You are given an n x n integer...

Rotting Oranges Problem

LeetCode 994. You are given an m x n grid...

Numbers With Same Consecutive Differences Problem

LeetCode 967. Return all non-negative integers of length n such...

K-Similar Strings Problem

LeetCode 854. Strings s1 and s2 are k-similar (for some...