# 675. Cut Off Trees for Golf Event

• Time: $O(m^2n^2)$
• Space: $O(mn)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 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>& forest) { auto compare = [&](const T& a, const T& b) { return a.height > b.height; }; priority_queue, 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 dirs{0, 1, 0, -1, 0}; int bfs(const vector>& forest, int si, int sj, int ei, int ej) { const int m = forest.size(); const int n = forest[0].size(); int steps = 0; queue> q{{{si, sj}}}; vector> seen(m, vector(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; }; }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 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> forest) { Queue 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> 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 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; }; }