675. Cut Off Trees for Golf Event LeetCode Solution
In this guide, you will get 675. Cut Off Trees for Golf Event LeetCode Solution with the best time and space complexity. The solution to Cut Off Trees for Golf Event problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Table of Contents
- Problem Statement
- Complexity Analysis
- Cut Off Trees for Golf Event solution in C++
- Cut Off Trees for Golf Event solution in Java
- Cut Off Trees for Golf Event solution in Python
- Additional Resources
Problem Statement of Cut Off Trees for Golf Event
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.
Note: The input is generated such that no two trees have the same height, and there is at least one tree needs to be cut off.
Example 1:
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:
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:
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] <= 109
Heights of all trees are distinct.
Complexity Analysis
- Time Complexity: O(m^2n^2)
- Space Complexity: O(mn)
675. Cut Off Trees for Golf Event LeetCode Solution in C++
struct T {
int i;
int j;
int height;
};
class Solution {
public:
int cutOffTree(vector<vector<int>>& forest) {
auto compare = [&](const T& a, const T& b) { return a.height > b.height; };
priority_queue<T, vector<T>, decltype(compare)> minHeap(compare);
for (int i = 0; i < forest.size(); ++i)
for (int j = 0; j < forest[0].size(); ++j)
if (forest[i][j] > 1)
minHeap.emplace(i, j, forest[i][j]);
int ans = 0;
int x = 0;
int y = 0;
while (!minHeap.empty()) {
const auto [i, j, _] = minHeap.top();
minHeap.pop();
// Walk from (x, y) to (i, j).
const int step = bfs(forest, x, y, i, j);
if (step < 0)
return -1;
ans += step;
x = i;
y = j;
}
return ans;
}
private:
static constexpr int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int bfs(const vector<vector<int>>& forest, int si, int sj, int ei, int ej) {
const int m = forest.size();
const int n = forest[0].size();
queue<pair<int, int>> q{{{si, sj}}};
vector<vector<bool>> seen(m, vector<bool>(n));
seen[si][sj] = true;
for (int step = 0; !q.empty(); ++step)
for (int sz = q.size(); sz > 0; --sz) {
const auto [i, j] = q.front();
q.pop();
if (i == ei && j == ej)
return step;
for (const auto& [dx, dy] : dirs) {
const int x = i + dx;
const int y = j + dy;
if (x < 0 || x == m || y < 0 || y == n)
continue;
if (seen[x][y] || forest[x][y] == 0)
continue;
q.emplace(x, y);
seen[x][y] = true;
}
}
return -1;
};
};
/* code provided by PROGIEZ */675. Cut Off Trees for Golf Event LeetCode Solution in Java
class T {
public int i;
public int j;
public int height;
public T(int i, int j, int height) {
this.i = i;
this.j = j;
this.height = height;
}
}
class Solution {
public int cutOffTree(List<List<Integer>> forest) {
Queue<T> minHeap = new PriorityQueue<>((a, b) -> Integer.compare(a.height, b.height));
for (int i = 0; i < forest.size(); ++i)
for (int j = 0; j < forest.get(0).size(); ++j)
if (forest.get(i).get(j) > 1)
minHeap.offer(new T(i, j, forest.get(i).get(j)));
int ans = 0;
int x = 0;
int y = 0;
while (!minHeap.isEmpty()) {
final int i = minHeap.peek().i;
final int j = minHeap.poll().j;
// Walk from (x, y) to (i, j).
final int step = bfs(forest, x, y, i, j);
if (step < 0)
return -1;
ans += step;
x = i;
y = j;
}
return ans;
}
private static final int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
private int bfs(List<List<Integer>> forest, int si, int sj, int ei, int ej) {
final int m = forest.size();
final int n = forest.get(0).size();
Queue<Pair<Integer, Integer>> q = new ArrayDeque<>(List.of(new Pair<>(si, sj)));
boolean[][] seen = new boolean[m][n];
seen[si][sj] = true;
for (int step = 0; !q.isEmpty(); ++step)
for (int sz = q.size(); sz > 0; --sz) {
final int i = q.peek().getKey();
final int j = q.poll().getValue();
if (i == ei && j == ej)
return step;
for (int[] dir : dirs) {
final int x = i + dir[0];
final int y = j + dir[1];
if (x < 0 || x == m || y < 0 || y == n)
continue;
if (seen[x][y] || forest.get(x).get(y) == 0)
continue;
q.offer(new Pair<>(x, y));
seen[x][y] = true;
}
}
return -1;
};
}
// code provided by PROGIEZ675. Cut Off Trees for Golf Event LeetCode Solution in Python
N/A
# code by PROGIEZAdditional Resources
- Explore all LeetCode problem solutions at Progiez here
- Explore all problems on LeetCode website here
Happy Coding! Keep following PROGIEZ for more updates and solutions.