1.题目

你被请来给一个要举办高尔夫比赛的树林砍树。树林由一个 m x n 的矩阵表示， 在这个矩阵中：

  • 0 表示障碍，无法触碰
  • 1 表示地面，可以行走

比 1 大的数 表示有树的单元格，可以行走，数值表示树的高度
每一步，你都可以向上、下、左、右四个方向之一移动一个单位，如果你站的地方有一棵树，那么你可以决定是否要砍倒它。
你需要按照树的高度从低向高砍掉所有的树，每砍过一颗树，该单元格的值变为 1（即变为地面）。
你将从 (0, 0) 点开始工作，返回你砍完所有树需要走的最小步数。 如果你无法砍完所有的树，返回 -1 。
可以保证的是，没有两棵树的高度是相同的，并且你至少需要砍倒一棵树。
image.png
image.png
提示：

  • m == forest.length
  • n == forest[i].length
  • 1 <= m, n <= 50
  • 0 <= forest[i][j] <= 109

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/cut-off-trees-for-golf-event
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2.思路

这里需要理解题目的意思，题目中需要从低到高砍掉所有的树，路过树可以选择不砍。我们要求的是砍掉所有树的最小步数，由于从低到高执行，所以我们可以依次将所有的树的高度排序记录其位置，然后按照这个顺序计算相邻树之间的最小距离，使用广度优先搜索来获得相邻两个位置的最小距离。

3.代码

  1. class Solution {
  2. public:
  3.     int direct[4][2] = {{-1,0}, {1,0}, {0,-1}, {0,1}};
  4.     int bfs(int bx, int by, int ex, int ey, vector<vector<int>> forest)
  5.     {
  6.         if(bx == ex && by == ey)
  7.             return 0;
  8.         int m = forest.size(), n = forest[0].size();
  9.         vector<vector<int>> visit(m, vector<int>(n, 0));
  10.         int step = 0;
  11.         visit[bx][by] = 1;
  12.         queue<pair<int,int>> q;
  13.         q.emplace(bx,by);
  14.         while(!q.empty())
  15.         {
  16.             step++;
  17.             int qz = q.size();
  18.             for(int i = 0; i < qz; i++)
  19.             {
  20.                 auto[x, y] = q.front();
  21.                 //cout << x <<" "<<y<<endl;
  22.                 q.pop();
  23.                 for(int j = 0; j < 4; j++)
  24.                 {
  25.                     int tx = x+direct[j][0], ty = y + direct[j][1];
  26.                     //cout << tx <<" "<<ty<<endl;
  27.                     if(tx>-1&&tx<m&&ty>-1&&ty<n)
  28.                     {
  29.                         if(!visit[tx][ty]&&forest[tx][ty]>0)
  30.                         {
  31.                             if(tx == ex && ty == ey)
  32.                             return step;
  33.                             //cout << "tx:" <<tx<<" ty:"<< ty<<endl;
  34.                             q.emplace(tx,ty);
  35.                             visit[tx][ty] = 1;
  36.                         }
  37.                     }
  38.                 }
  39.             }
  40.         }
  41.         return -1;
  42.     }
  44.     int cutOffTree(vector<vector<int>>& forest) {
  45.         int ans = 0;
  46.         vector<pair<int, int>> trees;
  47.         for(int i = 0; i < forest.size(); i++)
  48.         {
  49.             for(int j = 0; j < forest[0].size(); j++)
  50.             {
  51.                 if(forest[i][j] > 1)
  52.                 {
  53.                     trees.emplace_back(i, j);
  54.                 }
  55.             }
  56.         }
  57.         sort(trees.begin(), trees.end(), [&](const pair<int,int> &a, const pair<int, int> &b){
  58.             return forest[a.first][a.second] < forest[b.first][b.second];
  59.         });
  61.         int x = 0, y = 0, step;
  62.         for(int i = 0; i < trees.size(); i++)
  63.         {
  64.             step = bfs(x, y, trees[i].first, trees[i].second, forest);
  65.             //cout <<"bx:"<<x<<" by:"<<y<<" ex:"<<trees[i].first<<" ey:"<<trees[i].second <<" "<<step << endl;
  66.             if(step == -1)
  67.                 return -1;
  68.             ans += step;
  69.             x = trees[i].first;
  70.             y = trees[i].second;
  71.         }
  72.         return ans;
  73.     }
  74. };

此方法的时间复杂度和空间复杂度都比较高，后续还需优化。