<commit_before>// Time:  O(t * (logt + m * n)), t is the number of trees
// Space: O(t + m * n)

// Solution Reference: 
// 1. https://discuss.leetcode.com/topic/103532/my-python-solution-inspired-by-a-algorithm/2
// 2. https://discuss.leetcode.com/topic/103562/python-solution-based-on-wufangjie-s-hadlock-s-algorithm
// 3. https://en.wikipedia.org/wiki/A*_search_algorithm
// 4. https://cg2010studio.files.wordpress.com/2011/12/dijkstra-vs-a-star.png
class Solution {
public:
    int cutOffTree(vector<vector<int>>& forest) {
        const auto m = forest.size(), n = forest[0].size();
        priority_queue<pair<int, pair<int, int>>,
                       vector<pair<int, pair<int, int>>>,
                       greater<pair<int, pair<int, int>>> > min_heap;

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (forest[i][j] > 1) {
                    min_heap.emplace(forest[i][j], make_pair(i, j));
                }
            }
        }

        pair<int, int> start;
        int result = 0;
        while (!min_heap.empty()) {
            auto tree = min_heap.top(); min_heap.pop();
            int step = minStep(forest, start, tree.second, m, n);
            if (step < 0) {
                return -1;
            }
            result += step;
            start = tree.second;
        }
        return result;
    }

private:
    int minStep(const vector<vector<int>>& forest,
                const pair<int, int>& start,
                const pair<int, int>& end,
                const int m, const int n) {

        int min_steps = abs(start.first - end.first) + abs(start.second - end.second);
        unordered_set<int> lookup;
        vector<pair<int, int>> curr{start}, soon;
        while (true) {
            if (curr.empty()) {
                // cannot find a path in current stack from start to end,
                // try other possible paths in sooner stack with extra 2 steps
                swap(curr, soon);
                min_steps += 2;
            }
            if (curr.empty()) { // no any other possible path
                return -1;
            }
            int i, j;
            tie(i, j) = curr.back(); curr.pop_back();
            if (make_pair(i, j) == end) {
                return min_steps;
            }
            if (!lookup.count(i * n + j)) {
                lookup.emplace(i * n + j);
                vector<pair<pair<int, int>, bool>> expands = {{{i + 1, j}, i < end.first}, 
                                                              {{i - 1, j}, i > end.first},
                                                              {{i, j + 1}, j < end.second},
                                                              {{i, j - 1}, j > end.second}};

                for (const auto& expand : expands) {
                    int i, j;
                    bool is_closer;
                    tie(lvalue(tie(i, j)), is_closer) = expand;
                    if (0 <= i && i < m && 0 <= j && j < n &&
                        forest[i][j] && !lookup.count(i * n + j)) {
                        is_closer ? curr.emplace_back(i, j) : soon.emplace_back(i, j);
                    }
                }
            }
        }

        return min_steps;
    }<commit_msg>Update cut-off-trees-for-golf-event.cpp<commit_after>// Time:  O(t * (logt + m * n)), t is the number of trees
// Space: O(t + m * n)

// Solution Reference: 
// 1. https://discuss.leetcode.com/topic/103532/my-python-solution-inspired-by-a-algorithm/2
// 2. https://discuss.leetcode.com/topic/103562/python-solution-based-on-wufangjie-s-hadlock-s-algorithm
// 3. https://en.wikipedia.org/wiki/A*_search_algorithm
// 4. https://cg2010studio.files.wordpress.com/2011/12/dijkstra-vs-a-star.png
class Solution {
public:
    int cutOffTree(vector<vector<int>>& forest) {
        const auto m = forest.size(), n = forest[0].size();
        priority_queue<pair<int, pair<int, int>>,
                       vector<pair<int, pair<int, int>>>,
                       greater<pair<int, pair<int, int>>> > min_heap;

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (forest[i][j] > 1) {
                    min_heap.emplace(forest[i][j], make_pair(i, j));
                }
            }
        }

        pair<int, int> start;
        int result = 0;
        while (!min_heap.empty()) {
            auto tree = min_heap.top(); min_heap.pop();
            int step = minStep(forest, start, tree.second, m, n);
            if (step < 0) {
                return -1;
            }
            result += step;
            start = tree.second;
        }
        return result;
    }

private:
    int minStep(const vector<vector<int>>& forest,
                const pair<int, int>& start,
                const pair<int, int>& end,
                const int m, const int n) {

        int min_steps = abs(start.first - end.first) + abs(start.second - end.second);
        unordered_set<int> lookup;
        vector<pair<int, int>> straight{start}, detour;
        while (true) {
            if (straight.empty()) {
                // cannot find a path in the current expand stack which goes straightly from start to end,
                // try other possible paths in another expand stack with 2-step detour
                min_steps += 2;
                swap(straight, detour);
            }
            if (straight.empty()) { // no any other possible path
                return -1;
            }
            int i, j;
            tie(i, j) = straight.back(); straight.pop_back();
            if (make_pair(i, j) == end) {
                return min_steps;
            }
            if (!lookup.count(i * n + j)) {
                lookup.emplace(i * n + j);
                vector<pair<pair<int, int>, bool>> expands = {{{i + 1, j}, i < end.first}, 
                                                              {{i - 1, j}, i > end.first},
                                                              {{i, j + 1}, j < end.second},
                                                              {{i, j - 1}, j > end.second}};

                for (const auto& expand : expands) {
                    int i, j;
                    bool is_closer;
                    tie(lvalue(tie(i, j)), is_closer) = expand;
                    if (0 <= i && i < m && 0 <= j && j < n &&
                        forest[i][j] && !lookup.count(i * n + j)) {
                        is_closer ? straight.emplace_back(i, j) : detour.emplace_back(i, j);
                    }
                }
            }
        }

        return min_steps;
    }
{'fraction_non_alphanumeric': 0.13911077618688772, 'fraction_numerical': 0.012961567445365486, 'mean_word_length': 1.2663934426229508, 'pattern_counts': {'":': 0, '<': 65, '<?xml version=': 0, '>': 53, 'https://': 8, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 12, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '7540078', 'n_tokens_mistral': 2077, 'n_tokens_neox': 1930, 'n_words': 500}