【剑斩OFFER】算法的暴力美学——力扣 675 题：为高尔夫比赛砍树

一、题目描述

二、算法原理

思路：BFS 算法

1）找到图中不是0，1值，用个二维数组来存储他们的下标

2）排序，根据下标对应的值的大小升序

3）升序：1 -> 2 -> 3......... 的本质就是 1 —> 2 的最短路径，2——> 3 的最短路径等，所以剩下的

BFS 算法的老套路；

三、代码实现

class Solution { int dx[4] = {0,0,-1,1}; int dy[4] = {1,-1,0,0}; typedef pair<int,int> PII; int wight; int hight; public: int cutOffTree(vector<vector<int>>& ft) { wight = ft.size(); hight = ft[0].size(); vector<PII> index;//存储树的坐标 for(int i = 0; i < wight; i++) { for(int j = 0; j < hight; j++) { if(ft[i][j] > 1) index.push_back({i,j}); } } sort(index.begin(),index.end(),[&](PII x,PII y){//根据树的高度升序 return ft[x.first][x.second] < ft[y.first][y.second]; }); int bx = 0,by = 0;//起始点值 int total = 0; for(auto [ex,ey] : index)//终点值 { int sep = BFS(ft,bx,by,ex,ey);//查找目的值的步数 if(sep < 0) return -1;//找不到 total += sep; bx = ex;//更新起点值 by = ey; } return total; } int BFS(vector<vector<int>>& ft,int bx,int by,int ex,int ey) { //BFS 算法 if(bx == ex & by == ey) return 0;//有可能遍历到起始值 queue<PII> que; que.push({bx,by});//起点值 int ret = 0; bool vis[51][51];//标记是否遍历过入 queue 的下标 memset(vis,false,sizeof(vis));//清空 vis[bx][by] = true;//起点值已经遍历过了 while(que.size()) { int size = que.size(); ret++; while(size--)// 层数 { auto [x,y] = que.front(); que.pop(); for(int i = 0; i < 4; i++)// 上下左右遍历 { int a = x + dx[i]; int b = y + dy[i]; if(a >= 0 && b >= 0 && a < wight && b < hight && ft[a][b] && vis[a][b] == false) { if(a == ex && b == ey) { return ret;// 找到目标值 } que.push({a,b});//更新 vis[a][b] = true; } } } } return -1;//找不到 } };