資訊專欄INFORMATION COLUMN
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;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/72638.html
摘要：可以從頭邊同時(shí)進(jìn)行，查看葉子節(jié)點(diǎn)并加入到葉子節(jié)點(diǎn)鏈表遍歷一遍后，葉子節(jié)點(diǎn)鏈表為。將葉子節(jié)點(diǎn)保存下來。這個(gè)時(shí)候就會(huì)有第二層葉子節(jié)點(diǎn)那些在列表當(dāng)中為的點(diǎn)，用同樣的方法進(jìn)行剝除。最后留在葉子節(jié)點(diǎn)里面的點(diǎn)即可以為根。 題目： For a undirected graph with tree characteristics, we can choose any node as the root...
摘要：而根可以選擇從到的任意的數(shù)，唯一二叉樹的總數(shù)，就是根為到的樹相加。所以該問題化簡(jiǎn)為以為根，其唯一左子樹和右子樹各有多少，這就是個(gè)動(dòng)態(tài)規(guī)劃的問題了。 Unique Binary Search Trees I && II 解法請(qǐng)見：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...
摘要：在這里我們使用數(shù)組中下標(biāo)為的位置來記錄個(gè)元素可以組成的平衡二叉樹的數(shù)量。在遞歸的過程中，我們找到以當(dāng)前節(jié)點(diǎn)作為根節(jié)點(diǎn)的所有平衡二叉樹，并將結(jié)果以形式返回上一級(jí)調(diào)用。 題目要求 Given n, how many structurally unique BSTs (binary search trees) that store values 1...n? For example, Gi...
摘要：現(xiàn)在要求在這樣一棵生成樹中，找到生成樹的高度最低的所有根節(jié)點(diǎn)。然后利用鄰接表的相關(guān)屬性來判斷當(dāng)前節(jié)點(diǎn)是否是葉節(jié)點(diǎn)。度數(shù)為一的頂點(diǎn)就是葉節(jié)點(diǎn)。這里使用異或的原因是對(duì)同一個(gè)值進(jìn)行兩次異或即可以回到最初值。 題目 For an undirected graph with tree characteristics, we can choose any node as the root. The...
閱讀 2573·2023-04-25 14:54
閱讀 634·2021-11-24 09:39
閱讀 1845·2021-10-26 09:51
閱讀 3928·2021-08-21 14:10
閱讀 3521·2021-08-19 11:13
閱讀 2717·2019-08-30 14:23
閱讀 1832·2019-08-29 16:28
閱讀 3387·2019-08-23 13:45
