# Code language: Python classSolution: defcutOffTree(self, forest: List[List[int]]) -> int: n, m = len(forest), len(forest[0])
order = [(h, x, y) for x, row inenumerate(forest) for y, h inenumerate(row) if h > 1] order.sort()
dirs = ((0, 1), (0, -1), (1, 0), (-1, 0)) defwalk(cur, target): """ BFS """ if cur == target: return0 d = deque([cur]) vis = set() step = 0 while d: for _ inrange(len(d)): x, y = d.popleft() for i, j in dirs: dx, dy = x + i, y + j if dx < 0or dx >= n or dy < 0or dy >= m or forest[dx][dy] == 0: continue if (dx, dy) == target: return step + 1 if (dx, dy) notin vis: d.append((dx, dy)) vis.add((dx, dy)) step += 1 return -1 cur = (0, 0) ans = 0 for h, x, y in order: step = walk(cur, (x, y)) if step == -1: return -1 ans += step cur = (x, y) return ans
publicintcutOffTree(List<List<Integer>> forest) { intn= forest.size(), m = forest.get(0).size(); List<int[]> order = newArrayList<>(); for (inti=0; i < n; i++) { for (intj=0; j < m; j++) { if (forest.get(i).get(j) > 1) order.add(newint[] { forest.get(i).get(j), i, j }); } } Collections.sort(order, (a, b) -> a[0] - b[0]);
intx=0, y = 0, ans = 0; for (int[] cur : order) { intnx= cur[1], ny = cur[2]; intstep= walk(forest, x, y, nx, ny); if (step == -1) return -1; ans += step; x = nx; y = ny; } return ans; }
publicintwalk(List<List<Integer>> forest, int x, int y, int target_x, int target_y) { // BFS if (x == target_x && y == target_y) return0; intn= forest.size(), m = forest.get(0).size(); Deque<Integer> d = newArrayDeque<>(); d.addLast(x * 100 + y); Arrays.fill(vis, 0); intstep=0; while (!d.isEmpty()) { for (inti=0, s = d.size(); i < s; ++i) { intcur= d.pollFirst(); intcx= cur / 100, cy = cur % 100; for (int[] nxt : dirs) { intdx= cx + nxt[0], dy = cy + nxt[1]; if (dx < 0 || dx >= n || dy < 0 || dy >= m || forest.get(dx).get(dy) == 0) continue; if (dx == target_x && dy == target_y) return step + 1; intkey= dx * 100 + dy; if (vis[key] == 0) { d.addLast(key); vis[key] = 1; } } } step++; } return -1; } }
// Code language: Cpp using VI = vector<int>; using VII = vector<VI>; using PII = pair<int, int>; classSolution { public: int vis[5555]; VII dirs{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; intcutOffTree(vector<vector<int>>& forest){ int n = forest.size(), m = forest[0].size(); vector<PII> order; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { if (forest[i][j] > 1) order.push_back(PII{forest[i][j], i * 100 + j}); } } sort(order.begin(), order.end());
int x = 0, y = 0, ans = 0; for (PII& cur : order) { int nx = cur.second / 100, ny = cur.second % 100; int step = walk(forest, x, y, nx, ny); if (step == -1) return-1; ans += step; x = nx, y = ny; } return ans; }
intwalk(VII& forest, int x, int y, int target_x, int target_y){ // BFS if (x == target_x && y == target_y) return0; int n = forest.size(), m = forest[0].size(); deque<int> d; d.emplace_back(x * 100 + y); memset(vis, 0, sizeof(vis)); int step = 0; while (!d.empty()) { for (int i = 0, s = d.size(); i < s; ++i) { int cur = d.front(); int x = cur / 100, y = cur % 100; d.pop_front(); for (VI& nxt : dirs) { int dx = x + nxt[0], dy = y + nxt[1]; if (dx < 0 || dx >= n || dy < 0 || dy >= m || forest[dx][dy] == 0) continue; if (dx == target_x && dy == target_y) return step + 1; int key = dx * 100 + dy; if (vis[key] == 0) { d.emplace_back(key); vis[key] = 1; } } } step++; } return-1; } };