1#include <stdio.h>
2#include <stdlib.h>
3#include <stdbool.h>
4#include <limits.h>
5
6// Define directions for moving in the grid
7int directions[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
8
9// Function prototypes
10int bfs(int** forest, int m, int n, int sr, int sc, int tr, int tc);
11int cmpfunc(const void* a, const void* b);
12
13int cutOffTree(int** forest, int forestSize, int* forestColSize){
14    int m = forestSize;
15    int n = forestColSize[0];
16    
17    // Extract trees and sort by height
18    int trees[m*n][3], count = 0;
19    for (int i = 0; i < m; i++) {
20        for (int j = 0; j < n; j++) {
21            if (forest[i][j] > 1) {
22                trees[count][0] = forest[i][j];
23                trees[count][1] = i;
24                trees[count][2] = j;
25                count++;
26            }
27        }
28    }
29    qsort(trees, count, sizeof(trees[0]), cmpfunc);
30    
31    // Start cutting trees
32    int totalSteps = 0, sr = 0, sc = 0;
33    for (int i = 0; i < count; i++) {
34        int tr = trees[i][1];
35        int tc = trees[i][2];
36        int steps = bfs(forest, m, n, sr, sc, tr, tc);
37        if (steps == -1) return -1;
38        totalSteps += steps;
39        sr = tr;
40        sc = tc;
41    }
42    return totalSteps;
43}
44
45int bfs(int** forest, int m, int n, int sr, int sc, int tr, int tc) {
46    if (sr == tr && sc == tc) return 0;
47    bool visited[m][n];
48    for (int i = 0; i < m; i++) {
49        for (int j = 0; j < n; j++) {
50            visited[i][j] = false;
51        }
52    }
53    visited[sr][sc] = true;
54    int queue[m*n][2];
55    int front = 0, back = 0;
56    queue[back][0] = sr;
57    queue[back++][1] = sc;
58    int steps = 0;
59    while (front < back) {
60        int size = back - front;
61        steps++;
62        for (int i = 0; i < size; i++) {
63            int r = queue[front][0];
64            int c = queue[front][1];
65            front++;
66            for (int d = 0; d < 4; d++) {
67                int nr = r + directions[d][0];
68                int nc = c + directions[d][1];
69                if (nr >= 0 && nr < m && nc >= 0 && nc < n && !visited[nr][nc] && forest[nr][nc] > 0) {
70                    if (nr == tr && nc == tc) return steps;
71                    visited[nr][nc] = true;
72                    queue[back][0] = nr;
73                    queue[back++][1] = nc;
74                }
75            }
76        }
77    }
78    return -1;
79}
80
81int cmpfunc(const void* a, const void* b) {
82    int l = ((int*)a)[0];
83    int r = ((int*)b)[0];
84    return (l - r);
85}

1// C++ code snippet for implementing bidirectional BFS
2#include<vector>
3#include<queue>
#include<unordered_set>

using namespace std;

class Solution {
public:
    vector<vector<int>> directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    pair<int,int> serialize(int r, int c, int interCol) {
        return make_pair(r * interCol + c, 0);
    }

    vector<int> deserialize(int key, int interCol) {
        return {key / interCol, key % interCol};
    }

    int bidirectionalBFS(vector<vector<int>>& forest, int sr, int sc, int tr, int tc) {
        if (sr == tr && sc == tc) return 0;
        int m = forest.size(), n = forest[0].size();
        queue<pair<int, int>> q1, q2;
        unordered_set<int> visited1, visited2;
        q1.emplace(serialize(sr, sc, n));
        q2.emplace(serialize(tr, tc, n));
        visited1.insert(serialize(sr, sc, n));
        visited2.insert(serialize(tr, tc, n));
        int steps = 0;
        while (!q1.empty() && !q2.empty()) {
            // Always extend the smaller queue
            if (q1.size() > q2.size()) swap(q1, q2), swap(visited1, visited2);
            steps++;
            int sz = q1.size();
            while (sz--) {
                int key, dir;
                tie(key, dir) = q1.front(); q1.pop();
                vector<int> pos = deserialize(key, n);
                for (const vector<int> &direction : directions) {
                    int nr = pos[0] + direction[0], nc = pos[1] + direction[1];
                    int newKey = serialize(nr, nc, n);
                    if (nr >= 0 && nr < m && nc >= 0 && nc < n && forest[nr][nc] > 0) {
                        if (visited2.count(newKey)) return steps;
                        if (!visited1.count(newKey)) {
                            visited1.insert(newKey);
                            q1.emplace(newKey);
                        }
                    }
                }
            }
        }
        return -1;
    }

    int cutOffTree(vector<vector<int>>& forest) {
        vector<vector<int>> trees;
        int 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 sr = 0, sc = 0, total_steps = 0;
        for (auto& tree : trees) {
            int tr = tree[1], tc = tree[2];
            int steps = bidirectionalBFS(forest, sr, sc, tr, tc);
            if (steps == -1) return -1;
            total_steps += steps;
            sr = tr;
            sc = tc;
        }
        return total_steps;
    }
};