[LeetCode] 675. Cut Off Trees for Golf Event

MudOnTire 發布于2019-08-16 13:58 / 787人閱讀

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.

Solution

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;
    }
}

GPU云服務器云服務器 Golf Trees cut off

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/72638.html

Leetcode 310. Minimum Height Trees

摘要：可以從頭邊同時進行，查看葉子節點并加入到葉子節點鏈表遍歷一遍后，葉子節點鏈表為。將葉子節點保存下來。這個時候就會有第二層葉子節點那些在列表當中為的點，用同樣的方法進行剝除。最后留在葉子節點里面的點即可以為根。題目： For a undirected graph with tree characteristics, we can choose any node as the root...

xuxueli 2019-08-14 17:11 評論0 收藏0
[Leetcode] Unique Binary Search Trees 唯一二叉搜索樹

摘要：而根可以選擇從到的任意的數，唯一二叉樹的總數，就是根為到的樹相加。所以該問題化簡為以為根，其唯一左子樹和右子樹各有多少，這就是個動態規劃的問題了。 Unique Binary Search Trees I && II 解法請見：https://yanjia.li/zh/2019/02/... Given n, how many structurally unique BSTs (b...

enrecul101 2019-08-14 12:38 評論0 收藏0
[LeetCode] 96. Unique Binary Search Trees I &

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...

nidaye 2019-08-14 15:22 評論0 收藏0
leetcode95-96 Unique Binary Search Trees I-II

摘要：在這里我們使用數組中下標為的位置來記錄個元素可以組成的平衡二叉樹的數量。在遞歸的過程中，我們找到以當前節點作為根節點的所有平衡二叉樹，并將結果以形式返回上一級調用。題目要求 Given n, how many structurally unique BSTs (binary search trees) that store values 1...n? For example, Gi...

morgan 2019-08-15 11:06 評論0 收藏0
leetcode310. Minimum Height Trees

摘要：現在要求在這樣一棵生成樹中，找到生成樹的高度最低的所有根節點。然后利用鄰接表的相關屬性來判斷當前節點是否是葉節點。度數為一的頂點就是葉節點。這里使用異或的原因是對同一個值進行兩次異或即可以回到最初值。題目 For an undirected graph with tree characteristics, we can choose any node as the root. The...

xiaoxiaozi 2019-08-16 13:46 評論0 收藏0