Skip to content

Commit b42ace9

Browse files
fluency03fluency03
committed
CutOffTreesForGolfEvent675
1 parent d6dd9cb commit b42ace9

File tree

2 files changed

+145
-2
lines changed

2 files changed

+145
-2
lines changed

‎README.md‎

Lines changed: 3 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -44,11 +44,11 @@
4444
| [Graph](https://github.com/fluency03/leetcode-java/blob/master/src/graph) |
4545

4646

47-
# Total: 358
47+
# Total: 359
4848

4949
| Easy | Medium | Hard | - |
5050
|:----:|:-------:|:----:|:-:|
51-
| 95 | 198 | 61 | 4 |
51+
| 95 | 198 | 62 | 4 |
5252

5353

5454
| Question | Solution | Difficulty |
@@ -371,6 +371,7 @@
371371
| [661. Image Smoother](https://leetcode.com/problems/image-smoother/) | [Solution](https://github.com/fluency03/leetcode-java/blob/master/src/ImageSmoother661.java) | Easy |
372372
| [671. Second Minimum Node In a Binary Tree](https://leetcode.com/problems/second-minimum-node-in-a-binary-tree/) | [Solution](https://github.com/fluency03/leetcode-java/blob/master/src/SecondMinimumNodeInABinaryTree671.java) | Easy |
373373
| [674. Longest Continuous Increasing Subsequence](https://leetcode.com/problems/longest-continuous-increasing-subsequence/) | [Solution](https://github.com/fluency03/leetcode-java/blob/master/src/LongestContinuousIncreasingSubsequence674.java) | Easy |
374+
| [675. Cut Off Trees for Golf Event](https://leetcode.com/problems/cut-off-trees-for-golf-event/) | [Solution](https://github.com/fluency03/leetcode-java/blob/master/src/CutOffTreesForGolfEvent675.java) | Hard |
374375
| [677. Map Sum Pairs](https://leetcode.com/problems/map-sum-pairs/) | [Solution](https://github.com/fluency03/leetcode-java/blob/master/src/MapSumPairs677.java) | Medium |
375376
| [678. Valid Parenthesis String](https://leetcode.com/problems/valid-parenthesis-string/) | [Solution](https://github.com/fluency03/leetcode-java/blob/master/src/ValidParenthesisString678.java) | Medium |
376377
| [680. Valid Palindrome II](https://leetcode.com/problems/valid-palindrome-ii/) | [Solution](https://github.com/fluency03/leetcode-java/blob/master/src/ValidPalindromeII680.java) | Easy |

‎src/CutOffTreesForGolfEvent675.java‎

Lines changed: 142 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,142 @@
1+
/**
2+
* You are asked to cut off trees in a forest for a golf event. The forest is
3+
* represented as a non-negative 2D map, in this map:
4+
*
5+
* 0 represents the obstacle can't be reached.
6+
* 1 represents the ground can be walked through.
7+
*
8+
* The place with number bigger than 1 represents a tree can be walked through,
9+
* and this positive number represents the tree's height.
10+
*
11+
* You are asked to cut off all the trees in this forest in the order of tree's
12+
* height - always cut off the tree with lowest height first. And after cutting,
13+
* the original place has the tree will become a grass (value 1).
14+
*
15+
* You will start from the point (0, 0) and you should output the minimum steps
16+
* you need to walk to cut off all the trees. If you can't cut off all the trees,
17+
* output -1 in that situation.
18+
*
19+
* You are guaranteed that no two trees have the same height and there is at
20+
* least one tree needs to be cut off.
21+
*
22+
* Example 1:
23+
* Input:
24+
* [
25+
* [1,2,3],
26+
* [0,0,4],
27+
* [7,6,5]
28+
* ]
29+
* Output: 6
30+
*
31+
* Example 2:
32+
* Input:
33+
* [
34+
* [1,2,3],
35+
* [0,0,0],
36+
* [7,6,5]
37+
* ]
38+
* Output: -1
39+
*
40+
* Example 3:
41+
* Input:
42+
* [
43+
* [2,3,4],
44+
* [0,0,5],
45+
* [8,7,6]
46+
* ]
47+
* Output: 6
48+
*
49+
* Explanation: You started from the point (0,0) and you can cut off the tree in (0,0) directly without walking.
50+
*
51+
* Hint: size of the given matrix will not exceed 50x50.
52+
*
53+
*/
54+
55+
56+
public class CutOffTreesForGolfEvent675 {
57+
private int[][] directions = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
58+
public int cutOffTree(List<List<Integer>> forest) {
59+
if (forest == null || forest.size() == 0) return 0;
60+
PriorityQueue<TreePoint> pq = new PriorityQueue<>(1, Comparator.comparingInt(p -> p.h));
61+
int M = forest.size();
62+
int N = forest.get(0).size();
63+
int[][] golf = new int[M][N];
64+
int i = 0;
65+
for (List<Integer> level: forest) {
66+
int j = 0;
67+
for (Integer pos: level) {
68+
if (pos > 1) {
69+
pq.add(new TreePoint(i, j, pos));
70+
}
71+
golf[i][j] = pos;
72+
j++;
73+
}
74+
i++;
75+
}
76+
77+
Point pre = new Point(0, 0);
78+
int res = 0;
79+
80+
while (pq.size() > 0) {
81+
TreePoint t = pq.poll();
82+
Point dest = new Point(t.x, t.y);
83+
int d = minDistance(golf, pre, dest, M, N);
84+
if (d == -1) return -1;
85+
res += d;
86+
golf[t.x][t.y] = 1;
87+
pre = dest;
88+
}
89+
90+
return res;
91+
}
92+
93+
private int minDistance(int[][] golf, Point start, Point end, int M, int N) {
94+
if (start.x == end.x && start.y == end.y) return 0;
95+
Queue<Point> q = new LinkedList<>();
96+
q.add(start);
97+
boolean[][] visited = new boolean[M][N];
98+
visited[start.x][start.y] = true;
99+
int dist = 0;
100+
while (!q.isEmpty()) {
101+
int size = q.size();
102+
for (int i =0; i<size; i++) {
103+
Point curr = q.poll();
104+
if (curr.x == end.x && curr.y == end.y) return dist;
105+
for (int[] d: directions) {
106+
int x = curr.x + d[0];
107+
int y = curr.y + d[1];
108+
if (x == end.x && y == end.y) return dist + 1;
109+
if (x >= 0 && y >= 0 && x < M && y < N && !visited[x][y] && golf[x][y] != 0) {
110+
q.add(new Point(x, y));
111+
visited[x][y] = true;
112+
}
113+
}
114+
}
115+
dist++;
116+
}
117+
return -1;
118+
}
119+
120+
class Point {
121+
int x;
122+
int y;
123+
Point(int xx, int yy) {
124+
x = xx;
125+
y = yy;
126+
}
127+
}
128+
129+
class TreePoint {
130+
int x;
131+
int y;
132+
int h;
133+
TreePoint(int xx, int yy, int hh) {
134+
x = xx;
135+
y = yy;
136+
h = hh;
137+
}
138+
}
139+
140+
141+
142+
}

0 commit comments

Comments
 (0)