最少转弯路径算法：从BFS到0-1 BFS与Dijkstra的优化实践

1. 问题引入从地图导航到算法核心最近在复盘一些经典的图论与搜索问题时我又把“最少转弯问题”Minimum Turns Problem拿出来琢磨了一番。这个问题听起来很直白在一个二维网格比如城市地图、游戏地图上从起点到终点找到一条路径使得转弯的次数最少。它不像最短路径问题那样追求总距离最短而是追求“行驶最顺滑”。这在实际生活中太常见了——当你开车用导航时系统除了给你算最短距离、最快时间是不是也常常提供“大路优先”或“转弯少”的选项这背后考量的就是驾驶的便捷性和安全性频繁转弯不仅让司机手忙脚乱也增加了出错和事故的风险。在算法竞赛和面试中这个问题也堪称经典。它考察的不仅仅是对广度优先搜索BFS的基本掌握更是对状态定义和搜索策略的深刻理解。很多朋友第一次遇到这个问题时会下意识地套用标准BFS求最短路径的模板把每个网格点当作一个状态然后发现结果不对或者效率极低。这是因为标准BFS的“步数”在这里对应的是“移动的格子数”而我们关心的“代价”是“转弯的次数”这两个维度并不直接等价。如何将“转弯”这个动作量化并融入搜索过程就是解决这个问题的钥匙。今天我就结合自己多次实现和优化这个问题的经验从头到尾拆解一下“最少转弯问题”的解决思路。我们会从最直观但低效的暴力思路开始逐步深入到高效的双重BFS状态建模并探讨一些常见的变体和优化技巧。无论你是正在准备面试还是对算法优化感兴趣相信这篇内容都能给你带来一些实用的启发。2. 问题定义与初步分析为什么标准BFS会失效首先我们需要把问题描述得更精确一些。通常我们会得到一个M x N的网格。其中‘.’或0表示可以通行的空地。‘#’或1表示障碍物不可通行。给定起点坐标(start_x, start_y)和终点坐标(end_x, end_y)。移动规则每次可以向上、下、左、右四个方向之一移动一格但不能斜向移动且不能走出网格或进入障碍物格子。目标找到一条从起点到终点的可行路径使得整条路径中方向改变的次数最少。注意从起点开始的第一步不算一次转弯。为什么传统的、用于求最短步数曼哈顿距离类的BFS在这里不直接适用呢我们来看一个简单的例子。假设有一个 3x3 的空网格起点在(0,0)终点在(2,2)。S . . . . . . . E一条路径是(0,0) - (0,1) - (0,2) - (1,2) - (2,2)。这条路径转了两次弯在(0,2)处向右转变成向下在(1,2)处继续向下。 另一条路径是(0,0) - (1,0) - (2,0) - (2,1) - (2,2)。同样转了两次弯。 还有一条路径是(0,0) - (1,1) - (2,2)不这需要斜向移动规则不允许。 那么有没有只转一次弯的路径呢有(0,0) - (0,1) - (1,1) - (2,1) - (2,2)。看在(0,1)处向下转然后在(2,1)处向右转。等等这还是两次。 实际上在这个例子中最少转弯次数就是2。标准BFS会逐层扩展它首先找到的所有路径的“步数”移动格数都是4但它无法在步数相同的路径中区分出谁的转弯更少。BFS的队列保证的是“当第一次访问某个坐标时所用的步数是最少的”但它没有记录方向信息因此无法判断这次访问是否是以“更少转弯”的方式到达的。核心矛盾在于同一个坐标点可以从不同的方向以不同的“转弯代价”到达。标准BFS的状态(x, y)丢失了“从哪个方向来”这个关键信息而这对计算转弯代价至关重要。注意这里容易产生一个误区认为可以先用BFS求出所有最短路径步数最少的然后再从中选转弯最少的。这在某些简单场景可能可行但并不可靠。因为“转弯最少”的路径其“步数”可能比“最短步数”要长。我们的目标是转弯最少步数可以牺牲。所以必须修改搜索策略将“转弯次数”作为首要优化目标。3. 解决方案一带权BFS0-1 BFS的巧妙应用第一个高效的解决方案是利用0-1 BFS算法。这个算法适用于边权只有0和1两种值的图。在我们的问题中我们可以巧妙地定义“边权”如果沿着当前方向继续直走则移动的代价为0因为没有发生转弯。如果改变方向包括从起点开始的第一步虽然第一步不算转弯但我们可以将其视为一个“初始化”方向后的直走则移动的代价为1因为发生了一次转弯。这样一来问题就转化为了在一个图上求从起点状态到终点状态的路径使得路径的总权重即总转弯次数最小。这正是0-1 BFS的用武之地。3.1 状态设计与图建模首先我们需要重新定义搜索过程中的“状态”。一个完整的状态必须包含位置和方向。 我们可以定义状态为(x, y, dir)其中(x, y)是当前所在的网格坐标。dir是当前的前进方向通常用0,1,2,3代表上、右、下、左。那么状态之间的转移即图的边如何定义呢 从状态(x, y, dir)出发我们可以尝试两个动作直走沿着当前dir方向走一格到达新位置(nx, ny)。这个动作的代价是0。新状态的方向ndir保持不变仍是dir。转弯在当前点(x, y)改变方向。这本身不改变位置但产生了一个新方向ndirndir可以是除了当前dir及其反方向以外的其他方向这里需要仔细考虑。这个动作的代价是1。新状态是(x, y, ndir)。这里有一个关键细节“转弯”这个动作是否应该设计为一个停留在原地的状态转移在实际实现中更高效的做法不是显式地进行“原地转弯”而是在处理“直走”动作时允许从任何状态(x, y, dir)向四个方向尝试直走。如果尝试的方向ndir与当前状态的方向dir相同则代价为0如果不同则代价为1。这样我们就把“转弯”和“移动”合并到了一个动作里。3.2 算法流程与实现细节0-1 BFS使用一个双端队列deque来实现。算法流程如下初始化将起点的所有可能初始状态加入队列。起点没有前驱方向所以我们需要枚举从起点出发的第一步可能的方向。对于每个方向d状态(start_x, start_y, d)的初始转弯次数是0因为第一步不算转弯。将这些状态的距离设为0并加入双端队列的前端因为代价为0。队列循环当队列不为空时从队列前端弹出状态(x, y, dir)及其当前代价cost。终点判断如果(x, y)等于终点坐标我们可以记录cost为一种可能答案。但由于0-1 BFS的特性第一次弹出终点坐标的状态时其cost就是到达该状态的最小转弯次数。注意是弹出时确定而不是入队时。状态扩展对于当前状态(x, y, dir)枚举四个方向ndir(0,1,2,3)。计算沿ndir走一格后的新坐标(nx, ny)。检查(nx, ny)是否合法在网格内且不是障碍物。计算本次移动的代价delta如果ndir dir则delta 0否则delta 1。计算新代价new_cost cost delta。查询状态(nx, ny, ndir)的历史最小代价dist[nx][ny][ndir]。如果new_cost更小则更新dist并根据delta的值决定新状态的入队位置如果delta 0将(nx, ny, ndir)从队列前端加入。如果delta 1将(nx, ny, ndir)从队列后端加入。结果算法结束后检查所有终点坐标(end_x, end_y)对应的四个方向状态(end_x, end_y, dir)取其中dist值最小的一个即为最少转弯次数。如果均为无穷大则不可达。3.3 代码实现示例Pythonfrom collections import deque def min_turns(grid, start, end): :param grid: List[List[str]], . 可通行# 障碍 :param start: (int, int) 起点坐标 :param end: (int, int) 终点坐标 :return: 最少转弯次数若不可达返回 -1 if not grid or grid[start[0]][start[1]] # or grid[end[0]][end[1]] #: return -1 m, n len(grid), len(grid[0]) # 方向数组上右下左 dirs [(-1, 0), (0, 1), (1, 0), (0, -1)] # 距离数组初始化为无穷大 dist[x][y][dir] INF float(inf) dist [[[INF] * 4 for _ in range(n)] for _ in range(m)] dq deque() sx, sy start ex, ey end # 初始化将起点向四个方向出发的状态入队代价为0 for d in range(4): dist[sx][sy][d] 0 dq.appendleft((sx, sy, d, 0)) # (x, y, dir, cost) while dq: x, y, d, cost dq.popleft() # 如果弹出的是终点由于0-1 BFS的特性此时cost即为最小值之一 # 但为了严谨我们等循环结束后再统一取最小值 if (x, y) (ex, ey): # 可以直接返回cost因为队列是单调的先弹出的代价小 # 但为了处理所有状态我们选择更新答案最后再取最小 pass # 尝试向四个方向移动 for nd in range(4): nx, ny x dirs[nd][0], y dirs[nd][1] # 检查新位置合法性 if 0 nx m and 0 ny n and grid[nx][ny] .: delta 0 if nd d else 1 new_cost cost delta if new_cost dist[nx][ny][nd]: dist[nx][ny][nd] new_cost if delta 0: dq.appendleft((nx, ny, nd, new_cost)) else: dq.append((nx, ny, nd, new_cost)) # 找出到达终点的最小代价 ans min(dist[ex][ey]) return -1 if ans INF else ans # 测试用例 grid [ [., ., .], [., ., .], [., ., .] ] start (0, 0) end (2, 2) print(min_turns(grid, start, end)) # 输出应为 2实操心得与注意事项状态去重dist数组是三维的这至关重要。它确保了即使到达同一个坐标(x, y)如果来自不同的方向且代价更优仍然会被更新和再次扩展。这是与标准BFS使用二维visited数组最本质的区别。双端队列操作appendleft和append的使用必须与代价delta严格对应。代价为0的优先处理保证了算法的正确性类似于Dijkstra算法。起点初始化起点没有前驱方向所以我们需要虚拟四个初始方向。这相当于允许起点以0代价“选择”任何一个方向作为第一步的方向。空间复杂度状态数是O(M * N * 4)对于大多数比赛和面试场景是可以接受的。如果网格非常大例如上亿单元格则需要考虑其他优化或算法。4. 解决方案二Dijkstra算法与更一般的思路0-1 BFS是Dijkstra算法在边权仅为0或1时的特化和优化。实际上我们可以把这个问题直接建模为一个普通的有权图最短路径问题然后使用Dijkstra算法求解。这对于理解问题本质更有帮助也更容易扩展到边权更复杂的情况例如不同方向转弯代价不同。4.1 图模型构建图的节点顶点就是我们定义的状态(x, y, dir)。 图的边和权重的定义与0-1 BFS中完全一致从节点(x, y, dir)到节点(nx, ny, ndir)有一条有向边其中(nx, ny)是(x, y)向ndir方向移动一格后的位置。该边的权重为0如果ndir dir否则为1。这样问题就转化为在这个有向加权图中求从任意一个起点初始状态(start_x, start_y, d)d为0~3到任意一个终点状态(end_x, end_y, d’)的最短路径权重和最小。最后取所有起点状态到所有终点状态的最小距离即可。4.2 Dijkstra算法实现Dijkstra算法使用优先队列最小堆来保证每次扩展的都是当前已知距离最小的节点。import heapq def min_turns_dijkstra(grid, start, end): m, n len(grid), len(grid[0]) dirs [(-1, 0), (0, 1), (1, 0), (0, -1)] INF float(inf) dist [[[INF] * 4 for _ in range(n)] for _ in range(m)] sx, sy start ex, ey end pq [] # 优先队列(cost, x, y, dir) # 初始化起点 for d in range(4): dist[sx][sy][d] 0 heapq.heappush(pq, (0, sx, sy, d)) while pq: cost, x, y, d heapq.heappop(pq) # Dijkstra算法的性质第一次从堆中弹出某个状态时其cost就是最短距离 if (x, y) (ex, ey): # 我们可以直接返回cost因为终点状态第一次被弹出时即是最小值 # 但为了代码清晰我们也可以继续运行最后取min pass # 如果当前弹出的cost大于记录的距离说明是旧数据跳过 if cost dist[x][y][d]: continue for nd in range(4): nx, ny x dirs[nd][0], y dirs[nd][1] if 0 nx m and 0 ny n and grid[nx][ny] .: delta 0 if nd d else 1 new_cost cost delta if new_cost dist[nx][ny][nd]: dist[nx][ny][nd] new_cost heapq.heappush(pq, (new_cost, nx, ny, nd)) ans min(dist[ex][ey]) return -1 if ans INF else ans方案对比与选择时间复杂度0-1 BFS的时间复杂度是O(V E)其中V是状态数(M*N*4)E是边数约V*4。因为每个状态最多尝试4个方向。Dijkstra算法使用二叉堆的复杂度是O(E log V)。在边权仅为0和1的情况下0-1 BFS的效率通常更高。通用性Dijkstra算法更通用。如果问题变体中的转弯代价不再是固定的1比如左转和右转代价不同或者掉头代价更高那么Dijkstra算法可以轻松处理而0-1 BFS就不再适用。实现复杂度两者都需要三维距离数组逻辑复杂度相当。0-1 BFS需要小心操作双端队列Dijkstra需要维护优先队列。个人建议在明确是“最少转弯问题”即转弯代价为1直走代价为0时优先使用0-1 BFS因为它更高效。如果不确定代价模型或者需要处理更复杂的权重Dijkstra是更稳妥的选择。5. 常见变体与问题排查在实际编码和解题中你可能会遇到这个问题的各种变体也容易踩一些坑。5.1 问题变体输出具体路径不仅要求最少转弯次数还要输出一条具体的路径。这需要在状态中增加“前驱状态”的信息。在更新dist数组时同时记录是从哪个状态(px, py, pdir)以何种代价转移过来的。搜索结束后从终点状态反向回溯即可得到路径。注意路径中需要还原出经过的每个坐标点。允许“掉头”吗在基础问题中从方向上变为方向下即掉头通常也算作一次转弯delta1。我们的代码中ndir ! dir就视为转弯包含了掉头情况。如果某些场景规定掉头代价不同比如代价为2只需修改delta的计算逻辑。起点或终点在障碍物上这是常见的边界条件。必须在函数开始时就检查直接返回-1或特定标识。网格非常大但障碍物很少此时O(M*N*4)的状态数可能无法接受。可以考虑使用“射线法”或“跳跃BFS”进行优化。思路是从一个点出发沿着一个方向一直走直到撞到边界或障碍物这整条直线路径上的所有点如果以这个方向到达其转弯代价是相同的。这可以大幅减少需要显式入队的状态。这通常被称为“BFS on Grid with Sliding”或“0-1 BFS with Jumps”是这道题的一个高级优化技巧。5.2 典型错误与排查技巧使用二维visited数组这是最常见的错误。会导致搜索提前终止可能错过通过更多步数但更少转弯的路径。排查如果你的算法在某些测试用例上给出的答案比预期大或者找不到可行解但实际上存在首先检查是否错误地使用了二维去重。方向编码不一致在移动计算新坐标(nx, ny)和判断方向是否相同时使用的方向数组dirs必须一致。例如dirs[0] (-1,0)代表向上那么状态中的dir0也必须代表向上。排查用一个小网格如2x2手动模拟算法过程打印每个状态和转移检查坐标变化是否符合预期。起点/终点初始化错误起点状态的成本必须初始化为0。对于终点我们需要检查所有(end_x, end_y, dir)状态的最小值因为以任何方向到达终点都算成功。双端队列操作错误针对0-1 BFS误将代价为1的状态appendleft会破坏队列的单调性导致结果错误。排查可以同时实现Dijkstra版本作为对照。对于同一个测试用例比较两个算法的输出是否一致。忽略“第一步不算转弯”这个条件已经通过起点的初始化方式处理了。我们为起点创建了四个方向的状态成本都为0。这意味着从起点出发无论第一步朝哪个方向走都不计入转弯成本符合题意。调试小技巧在开发过程中可以增加一个简单的日志输出记录每次从队列中弹出状态的信息(x, y, dir, cost)以及每次成功更新状态的信息。用一个非常小的网格比如3x3全通来跟踪很容易发现状态转移是否符合逻辑。6. 性能优化与高级技巧跳跃BFS (BFS with Sliding)当网格尺寸巨大例如10^5 x 10^5但障碍物相对稀疏时前面提到的O(M*N*4)的状态空间是无法接受的。这时就需要用到跳跃BFS的思想。其核心在于利用网格的规则性只要方向不变移动的代价就是0。因此我们不应该一格一格地走而应该沿着一个方向“滑行”到底将这一整段直线路径作为一次扩展。6.1 算法思路我们不再定义(x, y, dir)为状态而是定义(x, y)为状态但BFS的层间代价是转弯次数。在标准BFS中我们从队列取出一个点然后尝试其四个邻居。在这里我们从队列取出一个点(x, y)以及到达它的转弯次数turns然后尝试四个方向。对于每个方向d我们不是只走一格而是沿着这个方向一直走直到撞到网格边界。撞到障碍物。到达终点。在这条“射线”上经过的所有可通行格子如果它们尚未被以相同或更少的转弯次数访问过那么它们都可以以turns如果是从起点直接开始或turns 1如果是改变方向后的代价到达。我们将这些点标记为已访问注意这里需要记录到达该点的最小转弯次数并将它们加入队列用于下一轮扩展。6.2 算法流程与实现要点数据结构使用一个队列queue存储(turns, x, y)。使用一个二维数组min_turns记录到达每个点的最小转弯次数初始化为无穷大。初始化起点(sx, sy)的min_turns设为-1或0根据第一步是否算转弯调整并将其四个方向能滑行到的所有点加入队列转弯次数设为0。这里的关键是从起点出发向四个方向滑行这“第一步”不算转弯。队列循环 a. 弹出(turns, x, y)。 b. 如果turns min_turns[x][y]跳过旧数据。 c. 尝试四个方向。对于每个方向从(x, y)的下一个格子开始滑行。 d. 沿着方向一直走对于沿途的每个点(nx, ny) * 如果(nx, ny)是终点更新答案可能是turns或turns1取决于是否改变方向。 * 如果(nx, ny)是障碍物或边界停止滑行。 * 如果turns 1 min_turns[nx][ny]说明找到了一条以更少转弯次数到达(nx, ny)的路径。更新min_turns[nx][ny] turns 1并将(turns 1, nx, ny)加入队列。 * 继续向该方向的下一个格子移动。 e. 注意滑行过程中如果遇到一个点其min_turns值已经小于等于turns注意不是turns1那么可以提前停止吗不可以。因为即使这个点已经以更少转弯次数被访问过它后面的点仍然可能通过当前这条路径以turns1的代价到达而这可能是更优的如果之前访问这个点的路径方向不同。所以我们必须滑行到底或者撞到障碍物/边界。结果终点的min_turns值即为答案。6.3 代码示意与复杂度分析from collections import deque def min_turns_jump_bfs(grid, start, end): m, n len(grid), len(grid[0]) dirs [(-1, 0), (0, 1), (1, 0), (0, -1)] INF float(inf) min_turns [[INF] * n for _ in range(m)] sx, sy start ex, ey end if grid[sx][sy] # or grid[ex][ey] #: return -1 dq deque() # 初始化起点从起点向四个方向滑行转弯次数为0 min_turns[sx][sy] -1 # 用-1表示起点方便处理也可以设为0 for d in range(4): nx, ny sx dirs[d][0], sy dirs[d][1] while 0 nx m and 0 ny n and grid[nx][ny] .: if min_turns[nx][ny] 0: # 第一次以0次转弯到达这些点 min_turns[nx][ny] 0 dq.append((0, nx, ny)) nx dirs[d][0] ny dirs[d][1] while dq: turns, x, y dq.popleft() if turns min_turns[x][y]: continue if (x, y) (ex, ey): # 可以提前结束因为队列是0-1 BFS先弹出的代价小 return turns # 尝试改变方向转弯 for nd in range(4): nx, ny x dirs[nd][0], y dirs[nd][1] while 0 nx m and 0 ny n and grid[nx][ny] .: new_turns turns 1 if new_turns min_turns[nx][ny]: min_turns[nx][ny] new_turns dq.append((new_turns, nx, ny)) nx dirs[nd][0] ny dirs[nd][1] return -1 if min_turns[ex][ey] INF else min_turns[ex][ey]复杂度分析在最坏情况下每个点仍然可能被四个方向访问但每个方向上的滑行会一次性处理一整排点。最坏时间复杂度可以认为是O(K * max(M, N))其中K是访问的“转折点”数量。在障碍物稀疏时K远小于M*N效率提升显著。空间复杂度为O(M*N)。注意事项这个版本的实现中队列操作实际上混合了0-1 BFS的思想因为直走代价0被隐含在初始化滑行中转弯代价为1。初始化部分将起点能直达的点以0代价入队主循环中每次扩展代表一次转弯代价1并滑行到底。实现时需要特别注意起点和终点的处理逻辑以及min_turns数组的初始值。