问题：

给定二维数组，每个格子：

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