675. Cut Off Trees for Golf Event

问题:

给定二维数组,每个格子:

  • 0:代表不可行走,不可种树
  • 1:代表可行走,未种树
  • x>1:代表,种了高x的树

从forest[0][0]开始出发,从最低高度的树开始砍伐,依次向更高的树前进进行砍伐。

问是否最终能砍完所有的树。

可以的话,返回行走步数。不可以的话,返回-1。

⚠️ 注意:从[0][0]开始出发,但不一定[0][0]的树高满足一开始就能砍伐的条件,有可能砍完别的树,还得回[0][0]来砍伐。

Example 1:
Input: forest = [[1,2,3],[0,0,4],[7,6,5]]
Output: 6
Explanation: Following the path above allows you to cut off the trees from shortest to tallest in 6 steps.

Example 2:
Input: forest = [[1,2,3],[0,0,0],[7,6,5]]
Output: -1
Explanation: The trees in the bottom row cannot be accessed as the middle row is blocked.

Example 3:
Input: forest = [[2,3,4],[0,0,5],[8,7,6]]
Output: 6
Explanation: You can follow the same path as Example 1 to cut off all the trees.
Note that you can cut off the first tree at (0, 0) before making any steps.
 
Constraints:
m == forest.length
n == forest[i].length
1 <= m, n <= 50
0 <= forest[i][j] <= 109

  

解法:BFS

思路:

  • 先根据给定的forest的各个位置的树高,构建树高结构体:treeh
    • {树高,i坐标,j坐标}
  • 将treeh按照【树高】进行从低到高排序。
    • 这即是我们要砍伐树木的顺序。
  • 从[0][0]开始,到treeh[0]->treeh[1]->treeh[2]...->treeh[n]
    • 任意两节点间都找到能走的最近的距离。相加即为最终结果。
    • 若两节点间不存在路径,直接返回-1。

 

求任意两节点【cur,des】间的最近距离,使用BFS

  • 将cur加入queue中,
  • 向四个方向,尝试走下一步,
    • 再从所有下一步,的四个方向,在尝试走下下一步...
  • 这其中每层queue即为一步。step++  -> level

 

在尝试过程中,下一步

  • 非法:触到边缘 | | visited=1访问过 | | forest=0不可走
  • 合法:
    • 找到dest,直接返回step
    • 未找到dest,当前节点入队。

⚠️  注意:

在queue构建中,尽量使用pair替代vector,可减少每次入队创建元素的花销

 

代码参考:

 1 class Solution {
 2 public:
 3     int m,n;
 4     int findShortest(vector<vector<int>>& forest, int curi, int curj, int desi, int desj) {
 5         //BFS: find shortest route from cur -> des
 6         if(curi==desi && curj==desj) return 0;
 7         vector<vector<int>> visited(n, vector<int>(m, 0));
 8         queue<pair<int,int>> q;//(i,j)
 9         //queue use pair instead of vector to avoid TLE err.
10         // cause inf while loop below, evey time to push queue, should construct a new vector.
11         vector<int> dir({-1,0,1,0,-1});
12         q.push({curi, curj});
13         visited[curi][curj]=1;
14         int step=0;//level
15         int sz=0;
16         int cur[2]={0};
17         while(!q.empty()) {
18             step++;
19             sz = q.size();
20             for(int k=0; k<sz; k++) {
21                 cur[0] = q.front().first;
22                 cur[1] = q.front().second;
23                 q.pop();
24                 for(int i=1; i<dir.size(); i++) {
25                     int nexti = cur[0]+dir[i-1];
26                     int nextj = cur[1]+dir[i];
27                     if(nexti<0 || nexti>=n || nextj<0 || nextj>=m 
28                        || visited[nexti][nextj]==1 || forest[nexti][nextj]==0)
29                         continue;
30                     if(nexti==desi && nextj==desj) return step;
31                     q.push({nexti, nextj});
32                     visited[nexti][nextj]=1;
33                 }
34             }
35         }
36         return -1;
37     }
38     int cutOffTree(vector<vector<int>>& forest) {
39         if(forest.empty() || forest[0].empty()) return 0;
40         vector<vector<int>> treeh;
41         int res=0;
42         n = forest.size();
43         m = forest[0].size();
44         //create treeheight structure: {high, i, j}
45         for(int i=0; i<n; i++) {
46             for(int j=0; j<m; j++) {
47                 if(forest[i][j]>1) {
48                     treeh.push_back({forest[i][j], i, j});
49                 }
50             }
51         }
52         //sort treeh by height from short->tall
53         sort(treeh.begin(), treeh.end());
54         //Start from [0][0]->treeh[0]
55         res = findShortest(forest, 0, 0, treeh[0][1], treeh[0][2]);
56         //then treeh[0]->treeh[1]...
57         int step = 0;
58         for(int i=1; i<treeh.size(); i++) {
59             //curtree=(treeh[i-1][1], treeh[i-1][2]);
60             //nexttree=(treeh[i][1], treeh[i][2]);
61             step = findShortest(forest, treeh[i-1][1], treeh[i-1][2], treeh[i][1], treeh[i][2]);
62             if(step==-1) return -1;
63             else res+=step;
64         }
65         return res;
66     }
67 };

 

上一篇:1005: 整数幂


下一篇:OpenStack使用Ceph存储,Ceph到底做了什么?