网格BFS等代价路径选择：如何筛选转弯数最多的最短路径

嘿，这个问题挺有意思的！确实不用大费周章生成所有路径再筛选，我们可以在搜索过程中就精准追踪那些最短路径里转弯最多的，下面给你几个实用的思路：

1. 扩展BFS的状态表示，记录转弯数 #

普通BFS只记录(x,y)位置和到达这里的最短步数，但我们可以把状态升级为**(x, y, 到达方向)**，同时给每个状态绑定两个关键值：

• 到达该点的最短步数
• 在最短步数下的最大转弯数

具体操作逻辑：

• 初始化起点(1,1)：可以设为「无方向」状态，步数为0，转弯数为0。
• 每次从当前状态扩展邻居时：
  • 如果是从「无方向」状态迈出第一步（比如走到(1,2)），新状态的步数+1，转弯数保持0，方向记为「右」。
  • 如果是从方向A走到方向B（比如从(1,2)的「右」方向走到(2,2)的「下」方向），新步数=原步数+1，转弯数=原转弯数 + 1（因为方向变了，多了一次转弯）；如果方向不变（比如从(1,2)继续走到(1,3)），转弯数不变。
• 更新规则：
  • 若新路径的步数比该状态已记录的步数更短：直接覆盖，记录新的步数和转弯数。
  • 若步数相同，但转弯数比已记录的更大：更新该状态的最大转弯数，并且继续扩展这个状态（因为它能带来转弯更多的后续路径）。

这种方法不会冗余处理，每个(x,y,方向)状态只会被更新有限次，效率和普通BFS差不多。

2. 先算最短距离，再定向搜索最多转弯路径 #

分两步走，逻辑更清晰：

1. 第一步：用普通BFS算出所有点到终点的最短距离（反向搜索更方便），得到dist[x][y]数组，这个数组能帮我们只走最短路径的分支。
2. 第二步：从起点出发，在最短路径约束下优先选转弯方向：
   • 每次移动时，必须满足「当前已走步数 + 下一个点到终点的最短距离 = 总最短距离」，这样就确保了走的是最短路径。
   • 在满足这个约束的前提下，优先选择和上一步方向不同的移动方向——这样每走一步都尽可能增加转弯数，最终得到的就是转弯最多的最短路径。

比如你的例子里，总最短距离是4（从(1,1)到(3,3)需要4步）。走到(1,2)后，下一步可选(1,3)和(2,2)：

• 到(1,3)的已走步数是2，dist[1][3]是2，2+2=4，符合约束；但方向和上一步相同，转弯数不增加。
• 到(2,2)的已走步数是2，dist[2][2]是2，2+2=4，符合约束；且方向和上一步不同，转弯数+1，所以优先走这个方向，最终得到转弯更多的路径。

3. 动态规划（DP）记录最优状态 #

定义DP数组dp[x][y][dir] = (min_steps, max_turns)，其中dir代表到达(x,y)时的移动方向（比如上、下、左、右，再加一个「初始无方向」）。

• 初始化：dp[1][1][无方向] = (0, 0)，其他状态初始为「无穷大步数，-1转弯数」。
• 状态转移：遍历每个状态的四个方向邻居，计算新的步数和转弯数，然后按照「先看步数是否更短，再看转弯数是否更大」的规则更新DP数组。
• 路径还原：最后从终点(3,3)的所有状态中，找到步数等于总最短距离且转弯数最大的那个状态，反向回溯就能得到完整路径。

这种方法和扩展BFS的思路本质类似，但用DP的方式更结构化，适合需要严谨推导的场景。

内容的提问来源于stack exchange，提问作者Cmeme