(C++) 675. Cut Off Trees for Golf Event
\n\nclass Solution {\npublic:\n    int cutOffTree(vector<vector<int>>& forest) {\n        int m = forest.size(), n = forest[0].size(), dir[5] = {-1, 0, 1, 0, -1
\n```\nclass Solution {\npublic:\n    int cutOffTree(vector<vector<int>>& forest) {\n        int m = forest.size(), n = forest[0].size(), dir[5] = {-1, 0, 1, 0, -1}; \n        bool seen[m][n]; \n        \n        auto fn = [&](pair<int, int>& start, pair<int, int>& end) {\n            int ans = 0; \n            memset(seen, false, sizeof(seen)); \n            seen[start.first][start.second] = true; \n            queue<pair<int, int>> q; q.push(start); \n            for (; q.size(); ++ans) \n                for (int sz = q.size(); sz; --sz) {\n                    auto [i, j] = q.front(); q.pop(); \n                    if (i == end.first && j == end.second) return ans; \n                    for (int k = 0; k < 4; ++k) {\n                        int ii = i + dir[k], jj = j + dir[k+1]; \n                        if (0 <= ii && ii < m && 0 <= jj && jj < n && forest[ii][jj] != 0 && !seen[ii][jj]) {\n                            seen[ii][jj] = true; \n                            q.emplace(ii, jj); \n                        }\n                    }\n                }\n            return -1; \n        }; \n        \n        vector<tuple<int, int, int>> vals; \n        for (int i = 0; i < m; ++i) \n            for (int j = 0; j < n; ++j) \n                if (forest[i][j] > 1) vals.emplace_back(forest[i][j], i, j); \n        sort(vals.begin(), vals.end()); \n        \n        int ans = 0; \n        pair<int, int> start = {0, 0}; \n        for (auto& [v, i, j] : vals) {\n            pair<int, int> end = {i, j}; \n            int val = fn(start, end); \n            if (val == -1) return -1; \n            ans += val; \n            start = end; \n        }\n        return ans; \n    }\n};\n```
['C']