675. Cut Off Trees for Golf Event Hard

1/**
2 * [675] Cut Off Trees for Golf Event
3 *
4 * 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:
5 * 
6 * 	0 means the cell cannot be walked through.
7 * 	1 represents an empty cell that can be walked through.
8 * 	A number greater than 1 represents a tree in a cell that can be walked through, and this number is the tree's height.
9 * 
10 * 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.
11 * 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).
12 * 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.
13 * 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.
14 *  
15 * Example 1:
16 * <img alt="" src="https://assets.leetcode.com/uploads/2020/11/26/trees1.jpg" style="width: 242px; height: 242px;" />
17 * Input: forest = [[1,2,3],[0,0,4],[7,6,5]]
18 * Output: 6
19 * Explanation: Following the path above allows you to cut off the trees from shortest to tallest in 6 steps.
20 * 
21 * Example 2:
22 * <img alt="" src="https://assets.leetcode.com/uploads/2020/11/26/trees2.jpg" style="width: 242px; height: 242px;" />
23 * Input: forest = [[1,2,3],[0,0,0],[7,6,5]]
24 * Output: -1
25 * Explanation: The trees in the bottom row cannot be accessed as the middle row is blocked.
26 * 
27 * Example 3:
28 * 
29 * Input: forest = [[2,3,4],[0,0,5],[8,7,6]]
30 * Output: 6
31 * Explanation: You can follow the same path as Example 1 to cut off all the trees.
32 * Note that you can cut off the first tree at (0, 0) before making any steps.
33 * 
34 *  
35 * Constraints:
36 * 
37 * 	m == forest.length
38 * 	n == forest[i].length
39 * 	1 <= m, n <= 50
40 * 	0 <= forest[i][j] <= 10^9
41 * 	Heights of all trees are distinct.
42 * 
43 */
44pub struct Solution {}
45
46// problem: https://leetcode.com/problems/cut-off-trees-for-golf-event/
47// discuss: https://leetcode.com/problems/cut-off-trees-for-golf-event/discuss/?currentPage=1&orderBy=most_votes&query=
48
49// submission codes start here
50
51impl Solution {
52    pub fn cut_off_tree(forest: Vec<Vec<i32>>) -> i32 {
53        0
54    }
55}
56
57// submission codes end
58
59#[cfg(test)]
60mod tests {
61    use super::*;
62
63    #[test]
64    fn test_675() {
65    }
66}
67