Problem
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:
0 represents the obstacle can"t be reached.
1 represents the ground can be walked through.
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.
class Solution {
public int cutOffTree(List> forest) {
List trees = new ArrayList<>();
for (int i = 0; i < forest.size(); i++) {
for (int j = 0; j < forest.get(0).size(); j++) {
int value = forest.get(i).get(j);
if (value > 1) trees.add(new int[]{i, j, value});
}
}
Collections.sort(trees, (a,b)->(a[2]-b[2]));
int res = 0, i = 0, j = 0;
for (int[] tree: trees) {
int dist = bfs(forest, i, j, tree[0], tree[1]);
if (dist < 0) return -1;
else {
res += dist;
i = tree[0];
j = tree[1];
}
}
return res;
}
private int[][] dirs = new int[][]{{-1,0},{1,0},{0,-1},{0,1}};
private int bfs(List> forest, int x, int y, int sx, int sy) {
int m = forest.size(), n = forest.get(0).size();
Queue queue = new LinkedList<>();
queue.offer(new int[]{x, y});
boolean[][] visited = new boolean[m][n];
visited[x][y] = true;
int dist = -1;
while (!queue.isEmpty()) {
int size = queue.size();
dist++;
for (int i = 0; i < size; i++) {
int[] cur = queue.poll();
if (cur[0] == sx && cur[1] == sy) return dist;
for (int[] dir: dirs) {
int nx = cur[0]+dir[0];
int ny = cur[1]+dir[1];
if (nx < 0 || ny < 0 || nx >= m || ny >= n ||
visited[nx][ny] || forest.get(nx).get(ny) <= 0) continue;
visited[nx][ny] = true;
queue.offer(new int[]{nx, ny});
}
}
}
return -1;
}
}
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/72638.html
摘要：可以从头边同时进行，查看叶子节点并加入到叶子节点链表遍历一遍后，叶子节点链表为。将叶子节点保存下来。这个时候就会有第二层叶子节点那些在列表当中为的点，用同样的方法进行剥除。最后留在叶子节点里面的点即可以为根。 题目： For a undirected graph with tree characteristics, we can choose any node as the root...
摘要：而根可以选择从到的任意的数，唯一二叉树的总数，就是根为到的树相加。所以该问题化简为以为根，其唯一左子树和右子树各有多少，这就是个动态规划的问题了。 Unique Binary Search Trees I && II 解法请见：https://yanjia.li/zh/2019/02/... Given n, how many structurally unique BSTs (b...
Unique Binary Search Trees Problem Given n, how many structurally unique BSTs (binary search trees) that store values 1...n? Example Given n = 3, there are a total of 5 unique BSTs. 1 3 3...
摘要：在这里我们使用数组中下标为的位置来记录个元素可以组成的平衡二叉树的数量。在递归的过程中，我们找到以当前节点作为根节点的所有平衡二叉树，并将结果以形式返回上一级调用。 题目要求 Given n, how many structurally unique BSTs (binary search trees) that store values 1...n? For example, Gi...
摘要：现在要求在这样一棵生成树中，找到生成树的高度最低的所有根节点。然后利用邻接表的相关属性来判断当前节点是否是叶节点。度数为一的顶点就是叶节点。这里使用异或的原因是对同一个值进行两次异或即可以回到最初值。 题目 For an undirected graph with tree characteristics, we can choose any node as the root. The...
阅读 2458·2023-04-25 14:54
阅读 527·2021-11-24 09:39
阅读 1768·2021-10-26 09:51
阅读 3821·2021-08-21 14:10
阅读 3457·2021-08-19 11:13
阅读 2671·2019-08-30 14:23
阅读 1777·2019-08-29 16:28
阅读 3327·2019-08-23 13:45
