## Cut Off Trees for Golf Event

• Time:O(m^2n^2)
• Space:O(mn)

## C++

``````struct T {
int i;
int j;
int height;
T(int i, int j, int height) : i(i), j(j), height(height) {}
};

class Solution {
public:
int cutOffTree(vector<vector<int>>& forest) {
auto compare = [&](const T& a, const T& b) { return a.height > b.height; };
priority_queue<T, vector<T>, decltype(compare)> minHeap(compare);

for (int i = 0; i < forest.size(); ++i)
for (int j = 0; j < forest[0].size(); ++j)
if (forest[i][j] > 1)
minHeap.emplace(i, j, forest[i][j]);

int ans = 0;
int x = 0;
int y = 0;

while (!minHeap.empty()) {
const auto [i, j, _] = minHeap.top();
minHeap.pop();
// walk from (x, y) to (i, j)
const int steps = bfs(forest, x, y, i, j);
if (steps < 0)
return -1;
ans += steps;
x = i;
y = j;
}

return ans;
}

private:
const vector<int> dirs{0, 1, 0, -1, 0};

int bfs(const vector<vector<int>>& forest, int si, int sj, int ei, int ej) {
const int m = forest.size();
const int n = forest[0].size();
int steps = 0;
queue<pair<int, int>> q{{{si, sj}}};
vector<vector<bool>> seen(m, vector<bool>(n));
seen[si][sj] = true;

while (!q.empty()) {
for (int s = q.size(); s > 0; --s) {
const auto [i, j] = q.front();
q.pop();
if (i == ei && j == ej)
return steps;
for (int k = 0; k < 4; ++k) {
const int x = i + dirs[k];
const int y = j + dirs[k + 1];
if (x < 0 || x == m || y < 0 || y == n)
continue;
if (seen[x][y] || forest[x][y] == 0)
continue;
q.emplace(x, y);
seen[x][y] = true;
}
}
++steps;
}

return -1;
};
};
``````

## JAVA

``````class T {
public int i;
public int j;
public int height;
public T(int i, int j, int height) {
this.i = i;
this.j = j;
this.height = height;
}
}

class Solution {
public int cutOffTree(List<List<Integer>> forest) {
Queue<T> minHeap = new PriorityQueue<>((a, b) -> a.height - b.height);

for (int i = 0; i < forest.size(); ++i)
for (int j = 0; j < forest.get(0).size(); ++j)
if (forest.get(i).get(j) > 1)
minHeap.offer(new T(i, j, forest.get(i).get(j)));

int ans = 0;
int x = 0;
int y = 0;

while (!minHeap.isEmpty()) {
final int i = minHeap.peek().i;
final int j = minHeap.poll().j;
// walk from (x, y) to (i, j)
final int steps = bfs(forest, x, y, i, j);
if (steps < 0)
return -1;
ans += steps;
x = i;
y = j;
}

return ans;
}

private static final int[] dirs = {0, 1, 0, -1, 0};

private int bfs(List<List<Integer>> forest, int si, int sj, int ei, int ej) {
final int m = forest.size();
final int n = forest.get(0).size();
int steps = 0;
Queue<int[]> q = new ArrayDeque<>(Arrays.asList(new int[] {si, sj}));
boolean[][] seen = new boolean[m][n];
seen[si][sj] = true;

while (!q.isEmpty()) {
for (int sz = q.size(); sz > 0; --sz) {
final int i = q.peek()[0];
final int j = q.poll()[1];
if (i == ei && j == ej)
return steps;
for (int k = 0; k < 4; ++k) {
final int x = i + dirs[k];
final int y = j + dirs[k + 1];
if (x < 0 || x == m || y < 0 || y == n)
continue;
if (seen[x][y] || forest.get(x).get(y) == 0)
continue;
q.offer(new int[] {x, y});
seen[x][y] = true;
}
}
++steps;
}

return -1;
};
}
``````