昨天把图灵平台刷到第九题这道题乍一看就是网格上带障碍物的最短路径实际上在最短路径上叠了一层“清除一整行/列”的技能限制。我一开始想着在普通BFS里加一个“技能是否已用”的标记就完事结果样例通过了提交的时候被后台数据教做人。后来冷静下来重新拆状态才意识到这道题真正考的是“状态设计”和“如何把重复BFS的代价降下来”。这篇就把我踩过的坑、从暴力到最优的完整推导过程都写出来给后面刷到同一题的朋友做个参考。这篇内容适合三类人看第一次接触“带操作次数限制”的搜索题想搞懂BFS状态边界的人已经知道分层BFS但发现这题直接加一维会错的人以及想通过一道题学会绝对值拆项优化的人。我会从最暴力的思路讲起最后给你一份可以直接跑通的完整代码并解释清楚为什么它能过大数据测试。1. 先搞清楚题目到底在问什么1.1 题目原文与样例题目描述大概是这样的给你一个 m 行 n 列的网格grid[i][j] 为 0 表示空地1 表示障碍物。你从左上角 (0,0) 出发要走到右下角 (m-1,n-1)每一步可以向上、下、左、右移动一格不能走出网格。现在给你一个技能可以选择某一行或者某一列把这一整行/列上的所有障碍物全部清除。技能只能使用一次。求从起点到终点的最短步数如果无法到达返回 -1。光说概念不够直观看一个具体例子。假设网格是0 1 0 1 1 0 0 0 0起点是左上角终点是右下角。如果不使用技能起点 (0,0) 的右侧是 1下方也是 1直接就被堵死了。但如果使用技能清除第 0 列网格会变成0 1 0 0 1 0 0 0 0这时候路径就可以走 (0,0) - (1,0) - (2,0) - (2,1) - (2,2)一共 4 步。如果清除第 1 行也能得到同样的效果。所以这个用例的答案就是 4。1.2 最容易看错的隐藏规则很多人看到“清除一行或一列”这个条件第一反应是做一个三维 BFSdist[i][j][0/1]0 表示技能还没用1 表示用过了。这个思路本身没错但这题不能用这么简单的状态原因我放在后面展开。这里先说两个容易误读的设定。第一技能清的是“一整行或一整列”不是单个障碍物也不是从当前位置朝某个方向清一条线。也就是说你选择清除第 r 行那么这一行上所有值为 1 的格子全部变 0而且这个效果是永久保持的后面再走到这些格子它们就是普通空地。第二使用技能不需要站在要清除的那一行/列上。你可以在任意时刻、任意位置选择任意一行或任意一列来清除。网上有不少讨论在这一步就理解偏了比如有人把技能写成“只能清除当前格子上的障碍物”还有人写成“清除当前朝向方向上的所有障碍物”这两个都和原题不符。状态设计一旦建立在错误前提上后面再优化都是白搭。2. 从暴力到最优解题思路的进化过程2.1 为什么“加一维 used”的普通 BFS 会翻车先说说我看到的最常见错误写法。很多人会定义一个三维数组 dist[x][y][used]used 取 0 或 1。转移逻辑是如果走到障碍格并且 used 0就可以把 used 改成 1然后把这个障碍格当作空地继续走。这个套路在“允许把一个障碍物变成空地”的题目里是完全正确的但在这题里不行。问题出在“清除一整行/列”这个范围效果上。假设你清除的是第 0 列那么 (1,0) 这个原本是 1 的格子会变成 0。如果只用一个 used 标记当 BFS 走到 (1,0) 时它确实会认为这个格子可以走但它不知道这个格子是被清除后才可以走的。更致命的是程序会把这个逻辑泛化只要 used 1碰到任意障碍格都当作空地处理。这等于把技能变成了“清掉全图所有障碍物”比题目的真实技能强太多结果自然偏小。遇到大数据时这种错误几乎无法通过样例暴露因为你手造的样例大概率不够刁钻。2.2 暴力枚举法把特殊技能翻译成 nm 次普通 BFS既然技能的影响范围是“一整行”或者“一整列”那最朴素的正确做法就是枚举。枚举清除第 0 行跑一次标准 BFS枚举清除第 1 行再跑一次…枚举清除第 0 列跑一次第 1 列再跑一次。每次 BFS 之前把对应行/列里的所有 1 临时改成 0跑完再恢复答案取所有次数的最小值。这个做法的时间复杂度是 O((nm) * n * m)。别嫌它笨它的正确性非常直观因为枚举覆盖了技能的全部可能性。更关键的是它非常适合拿来当对拍器。后面我写优化版本时就是用这个暴力版随机生成小网格对拍确认优化公式没有写偏。如果你自己实现我建议也先写一个枚举版再写优化版两边结果一致了再提交能省下大量调试时间。2.3 关键优化正反两次 BFS 为什么够用暴力法慢是因为每一次枚举都要完整跑一遍 BFS。但仔细想想清除第 r 行之后变化只发生在第 r 行内部。一条使用了这个技能的路径其实可以拆成三段起点沿着原始网格走到第 r 行上的某个点 A在第 r 行上水平移动到同行的点 B再从 B 沿着原始网格走到终点。中间为什么只能是一段水平移动因为如果路径在第 r 行上走了不止一段中间夹了一段非该行的路径你可以直接把这一段替换成第 r 行上两点之间的水平距离——网格中任何两点间的路径长度都不会小于曼哈顿距离而同一行两点间的曼哈顿距离就是列差替换后只会更短或相等。基于这个观察我们可以只跑两次普通 BFS一次从起点出发得到 distS[i][j]表示从起点不借助技能到达 (i,j) 的最短步数一次从终点出发得到 distT[i][j]表示从 (i,j) 不借助技能走到终点的最短步数。然后对每个被清除的候选行 r问题就变成了min over c1,c2: distS[r][c1] abs(c1 - c2) distT[r][c2]这里 c1 是进入第 r 行的列号c2 是离开第 r 行的列号。对候选列也做同样的处理只不过横向换成纵向。这样就绕开了“清行/清列”的动态状态把它变成了静态信息上的优化问题。2.4 绝对值拆项把 min 里讨厌的 abs 去掉公式虽然漂亮但如果直接对每行枚举 c1 和 c2复杂度是 O(m * n^2)比暴力还差。所以要把绝对值拆开。利用绝对值的基本性质分两种情况当 c1 c2 时distS[r][c1] abs(c1 - c2) distT[r][c2] distS[r][c1] - c1 distT[r][c2] c2当 c1 c2 时 distS[r][c1] c1 distT[r][c2] - c2第一种情况我们从左到右扫描这一行维护到目前为止的最小值 best min(distS[r][c] - c)那么对于当前列 c2就能用 best distT[r][c2] c2 更新答案。第二种情况从右到左扫描维护 best min(distS[r][c] c)再用 best distT[r][c] - c 更新答案。每一列被访问常数次处理所有行是 O(nm)处理所有列同理也是 O(nm)。这样总计就是 O(n*m)和两次 BFS 的复杂度同阶属于线性解法。3. 完整代码实现与关键细节3.1 Python 实现可以直接跑把上面的思路写成代码核心部分不长。我用 Python 写了一个完整版本注释写在关键位置from collections import deque def shortest_path_with_clear_skill(grid): m, n len(grid), len(grid[0]) INF 10**9 def bfs(sx, sy): dist [[INF] * n for _ in range(m)] if grid[sx][sy] 1: return dist dist[sx][sy] 0 q deque([(sx, sy)]) while q: x, y q.popleft() for dx, dy in ((1,0),(-1,0),(0,1),(0,-1)): nx, ny x dx, y dy if 0 nx m and 0 ny n and grid[nx][ny] 0 and dist[nx][ny] INF: dist[nx][ny] dist[x][y] 1 q.append((nx, ny)) return dist # distS: 从起点出发不借助技能到达每个格子的最短步数 # distT: 从终点出发不借助技能到达每个格子的最短步数 distS bfs(0, 0) distT bfs(m - 1, n - 1) # 不使用技能的情况 ans distS[m-1][n-1] # 枚举每一行作为被清除的行 for r in range(m): best_left INF for c in range(n): if distS[r][c] INF: best_left min(best_left, distS[r][c] - c) if best_left INF and distT[r][c] INF: ans min(ans, best_left distT[r][c] c) best_right INF for c in range(n - 1, -1, -1): if distS[r][c] INF: best_right min(best_right, distS[r][c] c) if best_right INF and distT[r][c] INF: ans min(ans, best_right distT[r][c] - c) # 枚举每一列作为被清除的列 for c in range(n): best_up INF for r in range(m): if distS[r][c] INF: best_up min(best_up, distS[r][c] - r) if best_up INF and distT[r][c] INF: ans min(ans, best_up distT[r][c] r) best_down INF for r in range(m - 1, -1, -1): if distS[r][c] INF: best_down min(best_down, distS[r][c] r) if best_down INF and distT[r][c] INF: ans min(ans, best_down distT[r][c] - r) return -1 if ans INF else ans # 样例测试 grid [ [0, 1, 0], [1, 1, 0], [0, 0, 0] ] print(shortest_path_with_clear_skill(grid))3.2 代码里每个细节为什么要这么写有几个细节需要单独拿出来说因为它们直接影响正确性。第一个是扫描顺序。在我的行扫描里我是先更新 best再计算答案。这样做是为了覆盖 c1 c2 的情况也就是进入第 r 行的点和离开第 r 行的点是同一个点。如果先计算再更新会漏掉这个方案。在一些题解里会看到先计算后更新的写法然后单独额外判断一次 c1 c2本质是一样的。第二个是 distS 和 distT 中 INF 的判断。原始网格中值为 1 的格子在两个 BFS 里都是不可达的所以 distS 和 distT 在这些位置都是 INF。只有 distS[r][c] INF 时才说明起点可以不借助技能走到这个格子此时它才有资格作为“进入被清除行/列”的入口。同理distT[r][c] INF 才说明从这个格子出发可以不借助技能走到终点才有资格作为出口。第三个是 INF 的取值。路径长度最大不会超过格点数也就是 m*n 级别一般题目里最多 10^6 左右。取 INF 10**9 足够大并且两个 INF 相加也不会变成负数。如果你用 C我建议用 0x3f3f3f3f而不是 INT_MAX因为 INT_MAX 加一个正数会溢出成负数届时所有比较都会乱掉。3.3 用样例手动推演一遍拿前面的样例来跑一遍手动推演。原始网格是0 1 0 1 1 0 0 0 0从起点出发的 BFS能走的格子其实只有 (0,0)因为右侧 (0,1) 是 1下方 (1,0) 也是 1所以 distS[0][0]0其余全是 INF。从终点出发的 BFS能走到 (2,2)、(2,1)、(2,0)、(1,2)、(0,2)所以这些位置的 distT 分别是 0、1、2、1、2。distS[2][2] 是 INF说明一开始不用技能是到不了终点的。接着看清除第 0 列的情况。我们按列扫描关注 c0 这一列。distS 里只有 (0,0) 不是 INFdistT 里 (2,0) 是 2。当扫描到 r2 时best_up 会取到 distS[0][0] - 0 0于是组合出的答案是 0 distT[2][0] 2 4。这正好对应路径 (0,0) - (1,0) - (2,0) - (2,1) - (2,2)完美吻合。手动推演的价值在于它能把抽象的公式落到实处写代码跑不通时你也能定位是 BFS 算错了还是扫描公式写错了。4. 复杂度对比与优化空间4.1 三种解法的复杂度对照这里把前面提到的三种思路做一个直观对比解法时间复杂度空间复杂度是否能处理大数据普通三维 BFS错误O(n*m)O(n*m)否状态语义不对枚举清除行/列 每次 BFSO((nm)nm)O(n*m)小数据可以n,m300 就吃紧正反 BFS 绝对值拆项O(n*m)O(n*m)可以线性复杂度第三种解法的空间复杂度是两个 dist 二维数组每个 m*n在 n 和 m 都在 1000 时用 Python 的 int 会稍微占内存但也是完全可以接受的。C 用 int 数组的话两个数组加起来约 8MB非常轻松。4.2 还能不能更快线性复杂度已经是这个模型下的极限了因为你至少要把每个格子读一遍所以很难有更优的算法复杂度。剩下的优化集中在常数层面比如把 deque 换成数组模拟队列把方向数组写成两个一维数组或者把行列扫描合并到一次循环里。在 Python 里这些优化能减少不少耗时在 C 里基本不需要刻意处理。有一个真正的空间优化思路如果你用的是 C可以让 distS 和 distT 复用同一个 vector或者只存储距离而不存储路径。但比存储更值得注意的是不要试图用 int8_t 或 short 来压缩距离因为距离可能超过 32767压缩反而引入 bug。4.3 这个技巧在哪些题目里能复用绝对值拆项是一个通用套路只要你最后算的东西长这样min over i,j: A[i] B[j] abs(i - j)就能用同样的方式拆成两种情况扫描。很多题目里都有它的身影比如两个有序数组找带距离约束的最小元素和、某种带“乘坐一段免费路线”的最短路问题、以及一些 DP 状态转移的优化。学会这一次以后遇到类似的 min 套绝对值结构可以直接想到扫描维护前缀/后缀最小值而不是傻傻地两层循环。分层状态加枚举技能目标的思路则在各种“带一次性技能的游戏寻路”题里经常出现。以后看到“玩家可以放一个技能改变地图局部形态”这类描述我的建议是先想清楚技能改变的是哪些格子的状态能不能用枚举覆盖覆盖之后能不能转化为静态信息。带着这个框架去解题比死记状态压缩套路要稳得多。5. 调试实录我踩过的坑和排查技巧5.1 坑一只加一维 used 的“假分层 BFS”我在写这题的第一版时用的就是 dist[i][j][2] 三维数组在遇到障碍格时把 used 从 0 改 1。样例完全没问题因为样例规模小技能清哪行效果都一样。提交后大数据 WA我才开始怀疑状态设计。这类“状态语义错但样例能过”的问题最坑人。排查方法很简单手写一个小网格让“清除单格”和“清除整行/列”产生差异。比如起点被障碍物围住但清除第 0 行后可以从起点横着走出去分层 BFS 只会清除起点的某一个邻居导致它认为需要绕更远的路甚至认为无解。我建议所有类似题都直接按这个思路设计反例而不是指望测试数据帮你看出来。5.2 坑二用 Dijkstra 或 0-1 BFS 反而把问题复杂化我还见过一种写法把“使用技能”建模成一条权为 0 的边然后跑 0-1 BFS。这个思路在清单格时是可行的但在这题里会导致状态爆炸因为你得记录到底清的是哪一行/哪一列。而且清整行/列的效果不是对一个点的 0 权转移而是改变一条线上所有点的连通性很难用边权模型优雅表达。所以最后还是回到枚举加正反 BFS。很多时候看起来更高级的图算法并不适合这种“局部地图永久改变”的场景反而是暴力枚举加静态预处理简洁可靠。5.3 测试用例怎么设计如果你写完代码想自测我强烈建议多构造下面这五类用例全 0 网格答案应该是 m n - 2。起点周围全是 1必须使用技能才能迈出第一步。终点周围全是 1必须使用技能才能进入终点。不使用技能也能到达且距离比使用技能更短或相等。无论清哪一行/哪一列都到不了终点返回 -1。第一类和最后一类特别能验证整体正确性。最后一类可以试这个网格0 1 1 1 1 1 1 1 1起点是 (0,0)终点是 (2,2)。清除第 0 列后(1,0) 和 (2,0) 会变成 0但到了 (2,0) 之后右侧的 (2,1) 还是 1终点依然不可达。清除第 2 行后(2,1) 和 (2,2) 变 0但起点到第 2 行之间全是 1过不去。结论就是 -1。5.4 一个关于 INF 选择的隐蔽教训在 Python 里我用 INF 10**9看起来没什么问题。但如果你用 float(inf)并且代码里有 distS[r][c] INF 这样的判断倒是能跑通一旦你把它参与加法运算得到 float 类型打印和后续比较都容易出问题。C 里如果用 INT_MAX 作为 INF两个 INF 相加会溢出成负数导致 ans 被错误更新。这类问题不会报编译错误但会以非常隐蔽的方式影响答案。统一用一个大整数并且保证“两倍 INF 也不溢出”是省心做法。我在调试时还有一个习惯在行列扫描之前先打印 distS 和 distT 两个矩阵肉眼确认 BFS 的结果是否符合预期。很多时候公式没写错而是前面的 BFS 因为边界条件写错了导致 dist 矩阵本身不对。这种分层排查的方法比盯着代码干想高效得多。6. 最后再分享一个自己的判断标准做了这么多题之后我慢慢总结出一个判断搜索题状态设计的小方法想清楚技能的每一次使用到底改变了哪些可达性关系。如果改变的是单个点用额外的维度记录技能次数就够了如果改变的是一整行、一整列甚至一片区域那么单纯压缩状态大概率会丢信息。这道题让我印象最深的不是正反 BFS也不是绝对值拆项而是“枚举技能目标”这个思路。很多看似需要复杂状态优化的题只要肯把所有技能目标枚举一遍问题就能退化成若干次普通搜索。再加上后续的静态信息复用复杂度又可以被拉回线性。这种“先暴力枚举再做信息复用”的思路比一开始就追求花哨的状态设计要稳得多。如果你也卡在图灵平台的第九题我建议你先写一版枚举答案再写一版扫描优化两边对拍通过后再提交。这样不仅能 AC还能真正吃透这题里的每一步推导。测完记得把那个“只加一维 used”的错解也留一份在本地以后遇到类似的带技能搜索题它会是一个很经典的警示案例。