<p>You are asked to cut off all the trees in a forest for a golf event. The forest is represented as an <code>m x n</code> matrix. In this matrix:</p>

<ul>
	<li><code>0</code> means the cell cannot be walked through.</li>
	<li><code>1</code> represents an empty cell that can be walked through.</li>
	<li>A number greater than <code>1</code> represents a tree in a cell that can be walked through, and this number is the tree&#39;s height.</li>
</ul>

<p>In one step, you can walk in any of the four directions: north, east, south, and west. If you are standing in a cell with a tree, you can choose whether to cut it off.</p>

<p>You must cut off the trees in order from shortest to tallest. When you cut off a tree, the value at its cell becomes <code>1</code> (an empty cell).</p>

<p>Starting from the point <code>(0, 0)</code>, return <em>the minimum steps you need to walk to cut off all the trees</em>. If you cannot cut off all the trees, return <code>-1</code>.</p>

<p><strong>Note:</strong> The input is generated such that no two trees have the same height, and there is at least one tree needs to be cut off.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/11/26/trees1.jpg" style="width: 242px; height: 242px;" />
<pre>
<strong>Input:</strong> forest = [[1,2,3],[0,0,4],[7,6,5]]
<strong>Output:</strong> 6
<strong>Explanation:</strong> Following the path above allows you to cut off the trees from shortest to tallest in 6 steps.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/11/26/trees2.jpg" style="width: 242px; height: 242px;" />
<pre>
<strong>Input:</strong> forest = [[1,2,3],[0,0,0],[7,6,5]]
<strong>Output:</strong> -1
<strong>Explanation:</strong> The trees in the bottom row cannot be accessed as the middle row is blocked.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> forest = [[2,3,4],[0,0,5],[8,7,6]]
<strong>Output:</strong> 6
<b>Explanation:</b> You can follow the same path as Example 1 to cut off all the trees.
Note that you can cut off the first tree at (0, 0) before making any steps.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == forest.length</code></li>
	<li><code>n == forest[i].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 50</code></li>
	<li><code>0 &lt;= forest[i][j] &lt;= 10<sup>9</sup></code></li>
	<li>Heights of all trees are <strong>distinct</strong>.</li>
</ul>

#include <iostream>
#include <vector>
#include <deque>
#include <tuple>
#include <unordered_map>
#include <array>
#include <map>

#define pop(QUEUE) QUEUE.front(); QUEUE.pop_front();
#define min(a, b) a < b ? a : b

class Solution {
public:
    using Cell = std::tuple<int, int>;
    using Forest = std::vector<std::vector<int>>;

    auto cell_id(const Forest& forest, const Cell& cell) -> int {
        auto [cell_x, cell_y] = cell;
        auto [forest_max_x, _] = std::tuple{ forest[0].size(), forest.size() };

        return cell_y * forest_max_x + cell_x;
    }

    auto valid_cell(const Forest& forest, const Cell& cell) -> bool {
        auto [cell_x, cell_y] = cell;
        auto [forest_max_x, forest_max_y] = std::tuple{ forest[0].size(), forest.size() };

        auto in_bounds = 0 <= cell_x && cell_x < forest_max_x &&
                         0 <= cell_y && cell_y < forest_max_y;

        if (!in_bounds) { return false; }

        auto walkable_cell = forest[cell_y][cell_x] != 0;
        return walkable_cell;
    }

    auto shortest_path(const Forest& forest, const Cell& start, const Cell& end) -> int {
        auto bfs_queue = std::deque<Cell>();
        auto distances = std::unordered_map<int, int>();
        
        bfs_queue.push_back(start);
        distances[cell_id(forest, start)] = 0;

        while (bfs_queue.size() > 0) {
            auto cell = pop(bfs_queue);
            if (cell == end) { break; }

            auto [cell_x, cell_y] = cell;
            auto dist_to_cell = distances[cell_id(forest, cell)];
            auto neighbour_cells = std::array<Cell, 4> {
                Cell { cell_x + 1, cell_y }, Cell { cell_x - 1, cell_y },
                Cell { cell_x, cell_y + 1}, Cell { cell_x, cell_y - 1 }
            };

            // for each neighbour cell check that its within bounds and a valid cell
            for (auto& neighbour : neighbour_cells) {
                if (valid_cell(forest, neighbour)) {
                    // we have visited this cell if there exists an entry for it in the distances array
                    auto neighbour_id = cell_id(forest, neighbour);
                    auto have_visited_neighbour = distances.find(neighbour_id) != distances.end();
                    if (!have_visited_neighbour) {
                        distances[neighbour_id] = 1 + dist_to_cell;
                        bfs_queue.emplace_back(neighbour);
                    }
                }
            }
        }

        auto end_cell_id = cell_id(forest, end);
        return distances.find(end_cell_id) == distances.end()
                    ? -1
                    : distances[end_cell_id];
    }


    auto cutOffTree(const Forest& forest) -> int {
        // build a heap of 
        auto tree_heap = std::map<int, Cell>();
        for (auto y = 0; y < forest.size(); y++) {
            for (auto x = 0; x < forest[0].size(); x++) {
                if (forest[y][x] > 1) {
                    tree_heap.emplace(forest[y][x], Cell {x, y});
                }
            }
        }

        auto last_tree_cell = Cell {0, 0};
        auto total_distance = 0;

        while (!tree_heap.empty()) {
            auto min_tree_iter = tree_heap.begin();
            auto [tree_size, tree_cell] = *min_tree_iter;

            auto distance = shortest_path(forest, last_tree_cell, tree_cell);
            if (distance == -1) {
                return -1;
            }

            total_distance += distance;
            last_tree_cell = tree_cell;

            tree_heap.erase(min_tree_iter);
        }

        return total_distance;
    }
};
453705