###### tags: `LeetCode` `BFS` `Queue` `Hard`
# LeetCode #675 [Cut Off Trees for Golf Event](https://leetcode.com/problems/cut-off-trees-for-golf-event/)
### (Hard)

你被請來給一個要舉辦高爾夫比賽的樹林砍樹。樹林由一個 m x n 的矩陣表示， 在這個矩陣中：

0 表示障礙，無法觸碰
1 表示地面，可以行走
比 1 大的數 表示有樹的單元格，可以行走，數值表示樹的高度
每一步，你都可以向上、下、左、右四個方向之一移動一個單位，如果你站的地方有一棵樹，那麼你可以決定是否要砍倒它。

你需要按照樹的高度從低向高砍掉所有的樹，每砍過一顆樹，該單元格的值變為 1（即變為地面）。

你將從 (0, 0) 點開始工作，返回你砍完所有樹需要走的最小步數。如果你無法砍完所有的樹，返回 -1 。

可以保證的是，沒有兩棵樹的高度是相同的，並且你至少需要砍倒一棵樹。

 

---
由於題目規定要按照樹的高度, 從矮的砍到高的, 因此先遍歷整個forest, 遇到樹時儲存{樹的高度, 列座標, 行座標}(使用tuple), 遍歷完後對樹的數組進行排序(會按照tuple的第一個數字排序, 也就是樹高)。

接下來, 從{0,0}開始(題目規定), 對每一個樹的位置進行BFS搜尋以找到最短路徑, 並將路徑長加至答案中, 而在下一輪中, 原先到達的樹的位置改為出發位置, 並再往後找下一個樹的位置(同樣使用BFS找最短路徑), 直到找到最後一個樹的位置, 並回傳加總後的答案(總路徑長)。

---

class Solution {
public:
    int m, n;
    int dir[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};
    int cutOffTree(vector<vector<int>>& forest) {
        vector<tuple<int, int, int>> trees;// height, x, y
        m = forest.size();
        n = forest[0].size();
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(forest[i][j]>1){
                    trees.push_back({forest[i][j], i, j});
                }
            }
        }
        sort(trees.begin(), trees.end());
        int ans = 0;
        int start_x = 0;
        int start_y = 0;
        for(auto& t:trees){
            int end_x = get<1>(t);
            int end_y = get<2>(t);
            int step = bfs(forest, start_x, start_y, end_x, end_y);
            if(step==INT_MAX)return -1;
            start_x = end_x;
            start_y = end_y;
            ans+=step;
        }
        return ans;
    }
    int bfs(vector<vector<int>>& forest, int start_x, int start_y, int end_x, int end_y){
        queue<pair<int, int>> q;
        vector<vector<int>> visited(m,vector<int>(n, 0));
        q.push({start_x, start_y});
        int step = 0;
        while(!q.empty()){
            for(int i=q.size();i>0;i--){
                pair<int, int> loc = q.front();q.pop();
                int x = loc.first;
                int y = loc.second;
                if(x == end_x && y ==end_y)return step;
                for(int j=0;j<4;j++){
                    int tmp_x = x + dir[j][0];
                    int tmp_y = y + dir[j][1];
                    if(tmp_x<0||tmp_y<0||tmp_x==m||tmp_y==n||forest[tmp_x][tmp_y]==0||visited[tmp_x][tmp_y]==1)continue;
                    q.push({tmp_x, tmp_y});
                    visited[tmp_x][tmp_y] = 1;
                }
            }
            step++;
        }
        return INT_MAX;
    }
};