企业官网建设流程全解析

第178场周赛这道题，我当时标了“未完成”，赛后复盘才发现它其实是一道非常标准的 0-1 BFS 最短路问题。题面给你的是一张 m x n 网格图，每个格子标着 1、2、3、4 四个方向，你要从左上角走到右下角。如果格子上的方向和你实际要走的方向不一致，就需要花 1 的代价去修改这个格子，问最少修改多少次，才能让这条路径变成一条“有效路径”。

当时卡住的原因很典型：我一直纠结在“到底改哪个格子、不改哪个格子”的决策上，觉得自己在做一个搜索加回溯的暴力题。但把模型转换一下，事情就简单了：每次从当前格子走到相邻格子，要么顺着格子原来的方向走，代价是 0；要么先花 1 把格子方向改掉再走，代价是 1。这样一来，整个网格就变成了一张边权只有 0 和 1 的有向图，从左上角到右下角跑一遍最短路径，答案就是最小修改次数。

如果你也经常打周赛，或者正在准备算法面试，这篇复盘值得看一下。我会从题意拆解讲到代码实现，再讲讲我当时为什么没做出来、以及怎么避免下次踩同样的坑。

1. 题意转换：把“改格子”变成“走图”

1.1 四个格子到底在说什么

题目给的网格里，每个格子的数字含义是这样的：

你从 (0, 0) 出发，目标是到达 (m-1, n-1)。如果当前格子上的箭头本来就指向你下一步想去的方向，你什么都不用做，直接走就行。如果箭头指向别的位置，而你偏要往其他方向走，就必须先花 1 的代价把这个格子修改成你要的方向，然后再走到相邻格。

这里要注意一个细节：“修改”是永久生效的。也就是说，如果一条最优路径经过了某个格子，而这个格子的方向被改过，那之后如果再经过这个格子，它就会按照修改后的方向去走。不过在正权图（或者说含 0 权边的图）里，最短路径不会出现重复经过同一个格子的情况，因为一旦出现环，把环去掉，总代价只会更小不会更大。所以这个细节在实际求解时不需要额外处理，直接用最短路模型就能覆盖。

1.2 一次移动等于一条带权边

把网格看成一个图，每个格子是一个节点，每次移动是一条有向边。对于当前格子 (x, y)，你理论上可以往上下左右四个方向走，但走到相邻格子的代价不是固定的：

• 如果你选择的方向正好等于 grid[x][y] 所指向的方向，边权为 0，这就是“免费边”。
• 如果你选择的方向不等于 grid[x][y]，边权为 1，因为你必须先把格子改过来才能走。

所以每个节点都会向外伸出 4 条有向边，其中 1 条权值是 0，另外 3 条权值是 1。整张图的边权只有 0 和 1 两类，这给后续选择算法留下了很大空间。

我举个生活化的例子帮助理解。你开一辆导航车，到了一个路口，如果路口指示牌本来就说“右转”，你右转就不用花钱；如果你非要直行或者左转，就得先花 1 块钱把指示牌改掉。现在要找到一条从起点到终点的路线，让花掉的钱最少。这个过程里，每一步的花费只取决于“你当前所在的路口”和“你想往哪个方向走”，和之前走过的路没有任何关系，这就把问题变成了最短路问题。

1.3 为什么是“最短路”而不是“搜索”

很多同学第一反应是“我用 DFS/BFS 枚举所有路径不就行了？”。但 DFS/BFS 枚举的是路径本身，路径数量在网格中是指数级的，根本枚举不完。而且普通 BFS 只能解决等权图的最短步数，遇到边权不同的情况就失效了。

这道题真正适合用最短路的原因在于它满足无后效性：从当前格子出发的最优决策，只取决于当前位置和当前格子的初始方向，不取决于你之前是从哪条路走过来的。这种“状态局部化”的结构，天然适合用最短路径算法去处理。把“修改了几次”定义为路径上的累计代价，问题就变成了一个非常清晰的单源最短路问题。

2. 解法选型：为什么是 0-1 BFS 而不是别的方法

2.1 朴素 BFS 为什么不对

普通 BFS 从起点出发，按“步数”一层一层向外扩展，第一次到达终点时，路径的步数一定最少。但这里我们要求的是“修改代价”最小，而不是步数最小，两者不一定是一回事。

举个最简单的解释：一条路径 2 步就能到终点，但每一步都要改方向，总代价是 2；另一条路径要绕 4 步，但每一步都顺着原来的箭头走，总代价是 0。普通 BFS 一定会先发现那条 2 步的路径，然后以为这就是答案，但真正的最优解显然是那条 4 步的路线。所以在边权不同的图上，按步数分层的 BFS 从一开始就走错了方向。

2.2 Dijkstra 能做，但不是最优选择

既然是求最短路，很多人会直接上 Dijkstra。Dijkstra 处理任意非负边权都没问题，这里边权只有 0 和 1，Dijkstra 当然能跑。但 Dijkstra 需要维护一个优先队列，每次弹出一个节点都要 log 级别的堆操作，复杂度是 O(E log V)。放在网格图里，E 大约是 4mn，V 是 mn，所以复杂度是 O(mn log(mn))。

如果网格很小，比如 100x100，Dijkstra 也能轻松跑完。但从算法本质的角度看，只用 0 和 1 两种边权的图，有专门更快的工具，用 Dijkstra 属于杀鸡用了牛刀，代码还更啰嗦。既然边权只有两种，我们完全可以把优先队列换成双端队列，把复杂度压到 O(V+E)。

2.3 0-1 BFS 的核心机制

0-1 BFS 是专门解决边权只有 0 和 1 的最短路算法。它维护一个双端队列，而不是普通队列：

• 从队头取出当前节点，扩展邻居时，如果边权为 0，就把邻居插到队头；
• 如果边权为 1，就把邻居插到队尾。

为什么这样能保证正确？关键在于双端队列的性质：任意时刻，队列里所有节点的 dist 值只会是相邻的两个整数，比如都是 d 或 d+1，不可能出现更大的值。因为 0 权边产生的节点代价不变，插到队头，不会打乱顺序；1 权边产生的节点代价加一，插到队尾，排在有相同代价节点的后面。于是队头弹出的节点始终是当前所有未处理节点中代价最小的，这其实就相当于是 Dijkstra 的一种特化版本，只是用双端队列替代了优先队列。

它的复杂度是 O(V+E)，在网格图中就是 O(mn)。如果网格的数据范围到了 1000x1000，Dijkstra 可能还会有一点压力，0-1 BFS 可以非常轻松地跑完。

3. 完整实现：双版本代码与易错点

3.1 Python 实现，带注释

我自己写的时候习惯先把方向数组固定成“右、左、下、上”的顺序，这样四个方向对应的下标刚好是 0、1、2、3，而格子里的数字 1、2、3、4 也刚好对应顺序，匹配起来非常直观：

from collections import deque class Solution: def minCost(self, grid: List[List[int]]) -> int: m, n = len(grid), len(grid[0]) # 方向编号：1=右，2=左，3=下，4=上 dx = [0, 0, 1, -1] dy = [1, -1, 0, 0] INF = 10 ** 9 dist = [[INF] * n for _ in range(m)] dist[0][0] = 0 dq = deque() dq.append((0, 0)) while dq: x, y = dq.popleft() for i in range(4): nx = x + dx[i] ny = y + dy[i] if nx < 0 or nx >= m or ny < 0 or ny >= n: continue # 如果当前格子本来就指向 i 对应的方向，代价为 0 # 否则需要先修改格子方向，代价为 1 cost = 0 if grid[x][y] == i + 1 else 1 nd = dist[x][y] + cost if nd < dist[nx][ny]: dist[nx][ny] = nd if cost == 0: dq.appendleft((nx, ny)) else: dq.append((nx, ny)) return dist[m - 1][n - 1]

这段代码的核心就两件事：用 dist 记录从起点到每个格子的当前最小代价；根据边权是 0 还是 1，决定把新格子放到队头还是队尾。代码跑完后，dist[m-1][n-1] 就是我们要求的答案。

3.2 C++ 实现要点

C++ 版本思路完全一样，区别只在容器和初始化方式：

class Solution { public: int minCost(vector<vector<int>>& grid) { int m = grid.size(), n = grid[0].size(); int dx[4] = {0, 0, 1, -1}; int dy[4] = {1, -1, 0, 0}; vector<vector<int>> dist(m, vector<int>(n, 1e9)); deque<pair<int, int>> dq; dist[0][0] = 0; dq.push_front({0, 0}); while (!dq.empty()) { auto [x, y] = dq.front(); dq.pop_front(); for (int i = 0; i < 4; ++i) { int nx = x + dx[i], ny = y + dy[i]; if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue; int w = (grid[x][y] == i + 1) ? 0 : 1; if (dist[x][y] + w < dist[nx][ny]) { dist[nx][ny] = dist[x][y] + w; if (w == 0) dq.push_front({nx, ny}); else dq.push_back({nx, ny}); } } } return dist[m - 1][n - 1]; } };

这里有个 C++ 的细节：dist 初始化的 INF 用 1e9 就行，不要用 INT_MAX，因为后面有 dist[x][y] + w 的操作，INT_MAX 加 1 会溢出变成负数，导致判断完全错乱。

3.3 五个高频易错点

我把实际写代码时最容易踩的坑列一下，这些坑每个我都踩过：

1. 方向编号对应错位。最容易犯的错误是把“1 向上”或者“2 向下”搞反。题目明确说 1 是右、2 是左、3 是下、4 是上，写方向数组时要严格按照这个顺序，否则全盘皆输。建议按我上面那样先写方向数组，再统一用 i+1 和 grid[x][y] 比较。

2. 忘记判断越界。这个属于比较低级的错误，但在键盘飞起来的时候很容易漏掉。越界判断必须放在 dist 更新之前，否则数组下标直接超范围，Python 可能报错，C++ 可能直接产生未定义行为。

3. dist 的初始值问题。如果用 -1 来初始化会让 0 权边无法处理，因为 0 权边更新后 dist 仍然是 0，无法区分“访问过且代价为 0”和“未访问”。正确做法是初始化成一个很大的数，比如 10**9。

4. 0 权边放队头、1 权边放队尾，这个顺序不能反。一旦反了，队列中节点的 dist 值不再单调，整个算法退化成错误的搜索，结果要么超时要么答案错误。我当时第一次手写 0-1 BFS 时就把边权判断写反了，结果样例都过不了，排查了很久才想起来是插入方向的问题。

5. 不需要在终点提前 break。很多人写最短路时习惯在弹出终点的一瞬间直接返回，觉得这样能省时间。0-1 BFS 里第一次弹出终点时它确实已经是最优解，这个做法本身没错，但如果你对算法性质不够熟悉，建议还是老老实实把循环跑完，最后再返回 dist[m-1][n-1]，这样逻辑更不容易出错。

4. 现场复盘：当时卡在哪一步，以及怎么调试

4.1 当时没做出来的真正原因

现在回头看，我卡住的原因非常清晰：我把这道题当成了“路径规划 + 格子修改”的组合问题，总想着要先决策改哪些格子，再决策怎么走。但我没有意识到，每个格子的方向只会影响到“从它出发的那一步”，不会影响后续格子的行为。也就是说，当前走到哪里、当前格子指向哪里，这两个信息已经足够决定下一步的所有可能性和代价，完全不需要回溯。

这就回到了最短路模型的核心直觉：如果你在一条路上做的事，只由“你当前在哪里”决定，而不由“你怎么来的”决定，那这件事就具有无后效性，就适合用图论最短路或动态规划来处理。以后遇到类似“求最小修改次数”的题，第一反应不要再是“枚举所有修改方案”，而是先把每次决策抽象成边权，看看是不是最短路。

4.2 手动模拟一个 2x2 小例子

数据范围越小，手动模拟越能验证代码逻辑。我用一个最经典的例子：grid = [[4, 1], [2, 3]]，也就是：

从 (0, 0) 出发，格子上是 4，指向向上，但向上越界，所以不能顺着走，只能改方向。有两种一步方案：

• 花 1 改成向右，走到 (0, 1)。此时 (0, 1) 的格子是 1，指向向右，想要到达终点 (1, 1) 必须向下，又得花 1 改方向，总代价为 2。
• 花 1 改成向下，走到 (1, 0)。此时 (1, 0) 的格子是 2，指向向左，想要到达终点 (1, 1) 必须向右，仍然要花 1 改方向，总代价为 2。

所以这个网格的答案就是 2。跑一遍 0-1 BFS 后，dist 矩阵会是：

[0, 1] [1, 2]

右下角的 2 就是答案。这个例子虽然简单，但用来验证方向数组和代价判断非常有效。我每次写完这类题，都会先跑一排 2x2 的用例，确保基础逻辑没问题，再上大样例。

4.3 调试工具与对拍方法

比赛时时间紧张，调试手段要简单粗暴。我最常用的调试方式是在 0-1 BFS 循环里打印 dist 矩阵的变化过程，确认每一轮的更新是否符合预期。如果 dist 出现了比正确答案更小的值，大概率是方向数组或代价判断写错了。

另外，想验证代码在高强度数据下有没有问题，可以写一个随机网格生成器，生成 m, n 不超过 5 的小网格，然后用暴力搜索（比如 DFS 枚举所有修改方案）算出答案，再和 0-1 BFS 的结果对拍。对拍几百组都一致，说明核心逻辑基本可信。对小网格暴力枚举是可行的，因为状态空间很小；大网格才必须用 0-1 BFS。

这个方法看起来笨，但非常有用。我自己比赛后复盘时，通常会先写一个对拍脚本跑一晚上，第二天醒来看到几百组数据全部通过，才敢说自己真正理解这道题了。

5. 从这道题延伸出去：一类题型的识别方法

5.1 边权 0/1 的题型套路

0-1 BFS 不是只在这一道题里出现，它是一大类题型的通用解法。判断方法其实很简单：如果每个状态转移的代价只有 0 和 1 两种，求最小总代价，就可以优先考虑双端队列 BFS。

举几个常见的变体：

• 迷宫里有些位置可以通过某些操作免费移动，其他位置移动需要花费 1，求最小代价。
• 二进制矩阵中，某类格子可以无代价切换状态，另外一些需要花费，求最少操作次数。
• 有向图中每条边要么免费要么收费 1，求起点到终点的最小花费。

这类题都有一个共同特点：状态数不会太大（因为要建图跑算法），但暴力枚举不可行。识别出“边权只有 0 和 1”这个特征，代码就能精准落地。

5.2 比赛后的复盘方法论

这道题我标了“未完成”，但赛后复盘得到的收获比当场 AC 一道水题大得多。我个人的复盘习惯是分三步：

第一步，不看题解，自己重新读一遍题，找出当时卡住的地方到底是一个知识点盲区，还是一个思维惯性问题。比如这道题，我是被“修改格子”这个操作迷惑了，没意识到它可以被抽象成边权。

第二步，看官方题解或者其他高赞题解，对比自己的思路差距在哪里，然后手写一遍完整代码，提交通过为止。

第三步，把这道题归类到自己的题型笔记里。记下“最小修改次数 + 网格 + 方向状态 = 0-1 BFS”，下次碰到类似表述，就能在几分钟内定位到正确模型。

我个人的实际体会是：周赛里遇到没写出来的题，不用太沮丧，这是最宝贵的学习机会。把复盘的每一步走完，比闷头刷十道简单题都有效。尤其是 0-1 BFS 这种图论技巧，代码量很短，但思维转换是关键，只要你亲手从“改格子”想到“最短路”，这个思路就会被牢牢记住。

最后再分享一个小技巧：如果你不确定一道题能不能用 0-1 BFS，就先问自己“我的每条边代价是不是只有 0 和 1？”如果是，就别急着写 Dijkstra 了，双端队列那几行代码，往往就是最优解。