元宝 LeetCode 675. Cut Off Trees for Golf Event Python3 Implement-北京尧图网络

Approach: Sort by Height BFS Between Consecutive TreesThe rules force a fixed order: trees must be cut shortest to tallest. So the walk decomposes into independent legs — go from your current cell to the next required tree by the shortest path, pay that distance, repeat. Shortest path on an unweighted grid with obstacles is BFS. If any leg is unreachable (a tree walled off by0s), return“-1”.from collections import dequefrom typing import Listclass Solution:def cutOffTree(self, forest: List[List[int]]) - int:if not forest or not forest[0]:return -1m, n len(forest), len(forest[0])def bfs(sr: int, sc: int, tr: int, tc: int) - int: Shortest step count from (sr,sc) to (tr,tc); -1 if unreachable. if sr tr and sc tc: return 0 seen [[False] * n for _ in range(m)] seen[sr][sc] True q deque([(sr, sc, 0)]) # (row, col, dist) while q: r, c, d q.popleft() for nr, nc in ((r 1, c), (r - 1, c), (r, c 1), (r, c - 1)): if 0 nr m and 0 nc n and not seen[nr][nc] and forest[nr][nc] 0: if nr tr and nc tc: return d 1 # early exit on hit seen[nr][nc] True # mark on enqueue q.append((nr, nc, d 1)) return -1 # Height 1 means a tree; cut in ascending height order. trees sorted((forest[r][c], r, c) for r in range(m) for c in range(n) if forest[r][c] 1) total row col 0 for _, tr, tc in trees: d bfs(row, col, tr, tc) if d -1: return -1 total d row, col tr, tc return totalKey detailsHeight“1” is walkable ground, not a tree. Only“ 1” enters the“trees” list — the classic bug here is treating“1” as a tree.“forest[nr][nc] 0” is the walkability test:“0” is blocked, everything else is passable (including trees you haven’t cut yet — you may walk over them).Mark“seen” on enqueue, not dequeue, or the same cell gets pushed repeatedly.Distance rides in the queue tuple, so no“dist[][]” grid per leg.Early return the moment the target is generated as a neighbor; no need to drain the queue.Sorting is by height only — heights are guaranteed distinct, so no tie-break needed.ComplexityTime: O(T · m · n) for T trees (one BFS per leg), plus O(T log T) to sort.Space: O(m · n) for“seen” and the queue, rebuilt per leg.Verified against the official cases:“[[1,2,3],[0,0,4],[7,6,5]] → 6”,“[[1,2,3],[0,0,0],[7,6,5]] → -1”,“[[2,3,4],[0,0,5],[8,7,6]] → 6”, and the large 4×4 case →“46”.

元宝 LeetCode 675. Cut Off Trees for Golf Event Python3 Implement

相关推荐

3D视觉Infra核心痛点与落地实践：从数据采集到线上监控

（论文速读）Sonata：摆脱几何捷径，学习可靠的点云自监督表征

Node-RED队列节流实战：用queue-gate解决消息丢包、乱序与雪崩

更多资讯

Python+大模型+微博舆情分析：从数据采集到可视化全链路实战指南

浅层模型与深度神经网络的选型之道：从特征工程到工程成本的全面对比

Qt通过COM操作Word生成文档：完整实战指南

Spring Boot四层XSS防御实战：过滤器+包装器+CSP+输出编码

U2-Flash 1M上下文实测：从能塞到能用的工程实践

双麦克风语音分离：基于GCC-PHAT与IVA的轻量级实时声源解耦方案

今日更新

悟空开源无代码平台实战：从实体建模到应用设计避坑指南

基于.NET9的多租户权限系统：数据权限与动态API落地实践

场地预约小程序毕设实战：SSM+微信小程序+MySQL数据库设计到避坑

本周精选

金融AI落地指南：从调研报告到技术选型与工程实践

大模型上下文成本与注意力优化技术深度解析——为何O(n²)平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测

基于GMM的语音识别系统原理与MATLAB实现详解

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？