文章目錄
- 題目鏈接:
- 題目描述:
- 解法
- C++ 算法代碼:
題目鏈接:
675. 為高爾夫比賽砍樹
題目描述:
解法
注意:砍樹要從低到高砍。
砍掉1,從1到5到2
砍掉2,從2到5到3
砍掉3,從3到5到2到6到4
砍掉4,從4到6到5
砍掉5,從5到6
砍掉6
變成若干個迷宮問題了。
把所有的最小值求出來然后加起來。
但是有個問題,你怎么知道砍樹的順序呢?
所以我們要先找到砍樹的順序,弄個二維數組先存一下下標和內容,然后按照內容由小到大排序。
C++ 算法代碼:
class Solution {int m, n; // 森林的行數和列數public:int cutOffTree(vector<vector<int>>& f) {m = f.size(), n = f[0].size();// 1. 準備工作:找出所有需要砍的樹,并按樹的高度排序vector<pair<int, int>> trees;for (int i = 0; i < m; i++)for (int j = 0; j < n; j++)if (f[i][j] > 1) // 樹的高度大于1才需要砍trees.push_back({i, j});// 按照樹的高度從小到大排序sort(trees.begin(), trees.end(),[&](const pair<int, int>& p1, const pair<int, int>& p2) {return f[p1.first][p1.second] < f[p2.first][p2.second];});// 2. 按照順序砍樹int bx = 0, by = 0; // 起始位置(0,0)int ret = 0; // 總步數for (auto& [a, b] : trees) {// 計算從當前位置到下一棵樹的最短步數int step = bfs(f, bx, by, a, b);if (step == -1) // 如果無法到達,返回-1return -1;ret += step; // 累加步數bx = a, by = b; // 更新當前位置}return ret;}bool vis[51][51]; // 訪問標記數組int dx[4] = {0, 0, 1, -1}; // 四個方向的x偏移量int dy[4] = {1, -1, 0, 0}; // 四個方向的y偏移量// BFS計算從起點(bx,by)到終點(ex,ey)的最短步數int bfs(vector<vector<int>>& f, int bx, int by, int ex, int ey) {if (bx == ex && by == ey) // 如果起點就是終點,返回0步return 0;queue<pair<int, int>> q;memset(vis, 0, sizeof vis); // 清空訪問標記q.push({bx, by});vis[bx][by] = true;int step = 0;while (q.size()) {step++;int sz = q.size();// 處理當前層的所有節點while (sz--) {auto [a, b] = q.front();q.pop();// 嘗試四個方向for (int i = 0; i < 4; i++) {int x = a + dx[i], y = b + dy[i];// 檢查新位置是否合法if (x >= 0 && x < m && y >= 0 && y < n && f[x][y] != 0 && !vis[x][y]) { // 0表示不能走的障礙物// 找到終點,返回當前步數if (x == ex && y == ey)return step;q.push({x, y});vis[x][y] = true;}}}}return -1; // 無法到達終點}
};