华为OD机试里的算法题刷多了会发现一个规律题干越贴近真实业务场景底层考点反而越朴素。这道智能驾驶路径规划题就是个典型——外壳是自动驾驶的网格地图内核却是BFS状态搜索和方向建模。今天我就把它从题干拆到代码用Python、Java、C各写一遍重点讲清楚“最少转弯次数”为什么不能靠二维visited数组硬套。不管你是正在刷OD机试的同学还是单纯想复习搜索类题目的开发者这篇都可以直接当模板用。1. 这道智能驾驶题到底考什么1.1 真题长什么样题目背景通常是这样的某个智能驾驶系统拿到了一张栅格地图地图由n行m列组成每个格子要么是1可通行要么是0障碍物。车辆从某个起点出发初始朝向固定为正东方向目标是到达终点格子。车辆每次可以选择直行一段距离也可以原地向左或向右转一次但转弯次数是代价。最终问你从起点到终点最少需要转几次弯如果根本到不了输出-1。输入格式大致如下5 5 1 1 1 1 1 1 0 0 0 1 1 1 1 0 1 1 0 1 0 1 1 1 1 1 1 0 0 4 4第一行是行数和列数接下来是地图最后一行是起点的x、y坐标和终点的x、y坐标。坐标一般从0开始但有些变种题会改成1开始读题要仔细。输出只有一个整数就是最少转弯次数。这个题在OD机试里属于“看着唬人、想明白就简单”的题型。智能驾驶、无人车、路径规划都是包装真正落在算法层面就是一个带方向的网格搜索。你甚至可以把它理解成“机器人在迷宫里走求最少转弯次数”的经典题型换了个马甲。1.2 它隐藏在表面之下的核心考点第一层考点是BFS这个大多数人都能看出来。但第二层考点才是关键搜索的状态不是“格子”而是“格子 当前朝向”。为什么这么说因为“转弯次数”和“步数”不一样。普通BFS求最短步数时一个格子只要被访问过之后再次访问一定不会更优所以二维visited数组就够了。但转弯次数不同同一个格子从东边方向进来和从北边方向进来后续能走的路线完全不同更优的可能性也存在。举个最直观的例子你站在同一个十字路口面朝东时只需要右转一次就能进某个岔路但如果面朝北可能需要左转两次甚至三次。如果只用二维visited第一次从某个方向到达这个格子后就把路堵死后面更优的方向组合就永远搜不到了。所以这道题的visited必须是三维的visited[x][y][dir]代表“以dir这个方向到达(x,y)”这件事是否已经处理过。这个设计是整个题目的灵魂也是多语言实现里最大的共性。理解了状态模型你会发现三个语言写出来的代码结构几乎一样方向数组、BFS队列、三维visited、遇到终点返回当前转弯次数。差别只来自语言本身的语法习惯。2. 解题思路为什么是“直行免费、转弯分层”的BFS2.1 贪心先撞墙的想法为什么不行很多人第一反应是“能直行就直行走不动了再转弯。”这就是典型的贪心思路。听上去很合理但架不住反例。假设地图是一个回字形通道起点在入口处终点在出口处。如果车一开始直行很快就撞到内墙被迫连续转弯如果一开始先转个弯绕到另一条通道反而能一路直行到底。贪心做局部最优只照顾眼前的方向根本看不到全局的弯道分布。再换个说法转弯次数是全局代价不是局部决策能决定的。你在某个格子选择直行可能让后面多转三次你选择转弯后面反而一次都不用转。这种决策之间的相互影响决定了只能老老实实用搜索枚举所有可能性。BFS在这里正好合适因为它天然按照“转弯次数从少到多”的层级向外扩展。第一次搜到的路径就是转弯次数最少的路径不需要像DFS那样反复回溯剪枝。2.2 把“转弯次数”当成搜索的层数普通BFS的层数是“步数”每走一步层数加1。这道题里我们需要把层数定义为“转弯次数”。那“直行”算什么呢直行不产生任何代价所以你在某一层内部可以随便沿着当前方向往前冲冲到障碍物挡住为止。这一整条直线上的所有格子都属于同一层。转弯才是进入下一层的门票。你每转一次代价加1然后又可以朝新方向一直开到障碍前。这个过程中所有以新方向直行能到达的格子都属于下一层。所以算法的自然写法是从当前状态出发先沿着当前方向把所有可直达格子全部入队再向左、向右各转一次把新方向能直达的格子作为“下一层”入队。队列弹出的时候如果到了终点当前记录的转弯次数就是答案。这里有一个容易踩的细节普通BFS如果发现终点可以直接返回因为队列按层展开这道题只要你按照“直行同一层、转弯进下一层”的方式入队同样可以保证第一次遇到终点就是最优转弯次数。2.3 方向数组和转向的编码技巧四个方向我习惯这样编码0东右 1南下 2西左 3北上对应的坐标增量是dx {0, 1, 0, -1} dy {1, 0, -1, 0}右转就是方向加1再取模(dir 1) % 4。左转就是方向加3再取模(dir 3) % 4。这里有个小坑有些同学会用(dir - 1 4) % 4写左转其实也行但加3取模更统一不容易写出负数。初始朝向是东也就是dir 0。起点状态就是(sx, sy, 0, 0)最后一位是转弯次数。后面代码里所有状态都带着这四个信息x、y、dir、turns。3. Python / Java / C 三语言实现与逐段讲解3.1 Python版用deque实现线性扩展Python写BFS队列首选collections.deque因为list.pop(0)是O(n)操作数据量一大就超时。from collections import deque def solve(): n, m map(int, input().split()) grid [list(map(int, input().split())) for _ in range(n)] sx, sy, ex, ey map(int, input().split()) dx [0, 1, 0, -1] dy [1, 0, -1, 0] # visited[x][y][dir]以dir方向到达(x,y)是否已经处理过 visited [[[False] * 4 for _ in range(m)] for _ in range(n)] q deque() q.append((sx, sy, 0, 0)) visited[sx][sy][0] True def push_line(x, y, direction, turns): nx x dx[direction] ny y dy[direction] while 0 nx n and 0 ny m and grid[nx][ny] 1 and not visited[nx][ny][direction]: visited[nx][ny][direction] True q.append((nx, ny, direction, turns)) nx dx[direction] ny dy[direction] while q: x, y, cur_dir, turns q.popleft() if x ex and y ey: print(turns) return # 沿当前方向继续直行转弯次数不变 push_line(x, y, cur_dir, turns) # 右转、左转转弯次数1 push_line(x, y, (cur_dir 1) % 4, turns 1) push_line(x, y, (cur_dir 3) % 4, turns 1) print(-1) if __name__ __main__: solve()push_line是核心函数。它的作用是从(x,y)出发沿着direction方向一直走把所有能到达的格子都加入队列。一旦遇到障碍、越界或者已经以这个方向访问过就停止。还有一点要注意push_line里遇到visited[nx][ny][direction] True就停止而不是跳过这个格子继续往前。原因我后面在踩坑篇详细解释这里先记住这个写法是正确的。如果输入数据很大可以把input()换成sys.stdin.buffer.read()做加速。OD机试的Python时间限制通常比较紧能用buffer尽量用buffer。3.2 Java版状态类与ArrayDequeJava实现里我习惯单独定义一个State内部类把x、y、dir、turns打包。虽然可以用数组存四个值但可读性差很多调试也费劲。import java.util.*; public class Main { static int n, m; static int[][] grid; static boolean[][][] visited; static int[] dx {0, 1, 0, -1}; static int[] dy {1, 0, -1, 0}; static class State { int x, y, dir, turns; State(int x, int y, int dir, int turns) { this.x x; this.y y; this.dir dir; this.turns turns; } } public static void main(String[] args) { Scanner sc new Scanner(System.in); n sc.nextInt(); m sc.nextInt(); grid new int[n][m]; for (int i 0; i n; i) { for (int j 0; j m; j) { grid[i][j] sc.nextInt(); } } int sx sc.nextInt(); int sy sc.nextInt(); int ex sc.nextInt(); int ey sc.nextInt(); visited new boolean[n][m][4]; QueueState queue new ArrayDeque(); queue.offer(new State(sx, sy, 0, 0)); visited[sx][sy][0] true; while (!queue.isEmpty()) { State cur queue.poll(); if (cur.x ex cur.y ey) { System.out.println(cur.turns); return; } pushLine(queue, cur.x, cur.y, cur.dir, cur.turns); pushLine(queue, cur.x, cur.y, (cur.dir 1) % 4, cur.turns 1); pushLine(queue, cur.x, cur.y, (cur.dir 3) % 4, cur.turns 1); } System.out.println(-1); } static void pushLine(QueueState queue, int x, int y, int dir, int turns) { int nx x dx[dir]; int ny y dy[dir]; while (nx 0 nx n ny 0 ny m grid[nx][ny] 1 !visited[nx][ny][dir]) { visited[nx][ny][dir] true; queue.offer(new State(nx, ny, dir, turns)); nx dx[dir]; ny dy[dir]; } } }Java细节里有几个点值得提。第一队列推荐ArrayDeque而不是LinkedList性能更好。第二Scanner在数据量较大的时候不算快但OD机试的输入规模通常还能接受如果遇到超大输入可以换BufferedReader手写解析。第三visited三维数组初始化默认就是false不需要手动赋值。pushLine是static方法因为要访问静态的grid和visited。如果不想全写静态也可以把方法放在类里用实例变量但机试时静态到底是最省事的写法。3.3 C版结构体、Lambda与性能细节C版本是我觉得最干脆的。用结构体存状态用Lambda封装pushLine代码紧凑运行也快。#include bits/stdc.h using namespace std; struct State { int x, y, dir, turns; }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; vectorvectorint grid(n, vectorint(m)); for (int i 0; i n; i) { for (int j 0; j m; j) { cin grid[i][j]; } } int sx, sy, ex, ey; cin sx sy ex ey; int dx[4] {0, 1, 0, -1}; int dy[4] {1, 0, -1, 0}; vectorvectorvectorbool visited( n, vectorvectorbool(m, vectorbool(4, false)) ); queueState q; q.push({sx, sy, 0, 0}); visited[sx][sy][0] true; auto pushLine [](int x, int y, int dir, int turns) { int nx x dx[dir]; int ny y dy[dir]; while (nx 0 nx n ny 0 ny m grid[nx][ny] 1 !visited[nx][ny][dir]) { visited[nx][ny][dir] true; q.push({nx, ny, dir, turns}); nx dx[dir]; ny dy[dir]; } }; while (!q.empty()) { State cur q.front(); q.pop(); if (cur.x ex cur.y ey) { cout cur.turns \n; return 0; } pushLine(cur.x, cur.y, cur.dir, cur.turns); pushLine(cur.x, cur.y, (cur.dir 1) % 4, cur.turns 1); pushLine(cur.x, cur.y, (cur.dir 3) % 4, cur.turns 1); } cout -1 \n; return 0; }C的vectorvectorvectorbool虽然写着麻烦但安全。如果你确定地图最大不超过100也可以用bool visited[105][105][4]这种静态数组性能更好代码更短但存在数组越界的风险。ios::sync_with_stdio(false)和cin.tie(nullptr)这两行建议直接背下来。不加的话cin在大输入下可能比scanf慢不少加了之后基本持平。Lambda里用[]捕获所有外部变量方便直接访问grid、visited和q。3.4 三份代码的差异与共性三份代码其实只有一个pushLine函数的差别其余骨架完全一样。这里用表格对比一下关键差异方便你在考场上快速切换语言对比项PythonJavaC队列类型dequeArrayDequequeue状态保存元组四个值State内部类State结构体visited构建嵌套列表三维boolean数组三维vector方向数组列表int数组int数组边界判断0 nx n 链式分段比较分段比较性能较慢但写法最快中等最快共性是都按“先直行、再左右转”的顺序扩展都只在入队时标记visited出队时判断是否到达终点。这里有个特别容易忽略的点为什么终点判断放在出队而不是入队时判断因为入队时判断存在一个隐患同一层可能有多个格子都能到达终点但你先入队的那个格子可能不是转弯次数最少的路径上的终点。虽然实际上同一层入队的格子转弯次数相同但如果你在入队时提前return可能遇到的是“先入队但方向还没最优”的状态。出队时判断最保险因为队列按照转弯次数严格分层第一个弹出的终点必然是最优的。4. 实战踩坑记录与问题排查清单4.1 用二维visited过滤答案偏大甚至死循环这是新人最容易犯的错。看到是网格题下意识就开一个visited[n][m]每个格子只访问一次。然后发现有的样例输出比预期大甚至直接死循环。原因前面已经说了同一个格子从不同方向进入后续需要的转弯次数完全不同。如果你只记录“格子是否访问过”就可能把某个更优方向组合过滤掉导致答案偏大。打个比方你在十字路口中央从东边来和从西边来虽然都站在同一个路口但接下来去南边的难度完全不一样。二维visited强行把这两个状态当成同一个等于让司机失忆忘了自己是从哪个方向来的。解决方式就是升级成三维visited。这一步做完这道题基本就稳了。4.2 pushLine遇visited就停还是会漏掉后面格子有同学会问pushLine在while循环里遇到visited[nx][ny][dir] true就停但如果中间某个点被访问过后面的点还没被访问过怎么办会不会漏状态这个担心是多余的原因在于pushLine的填充方式它每次都是沿着同一个方向一条线填到底。如果某个格子之前已经以dir方向访问过那么当时一定是沿着dir方向一路填过来的这个格子后面的所有连续可通行格子也一定全部被访问过了。换句话说同方向访问具有连续性。你遇到一个已访问的点意味着这一整条射线后面的点都已经处理过了继续往后试探只会造成大量重复状态入队白白增加时间开销。当然如果你改成了“逐格走”的普通BFS写法那遇到visited就不能随便停因为你是跳着走的。不同写法对应不同规则别生搬硬套。4.3 起点和终点的几个阴间细节第一起点就是终点的情况。有些题目认为车还没出发就到达答案是0有些题目要求车必须动一下才算。绝大多数情况下是输出0但保险起见可以看样例。第二初始方向。本题固定朝东但变种题可能让你读入初始方向甚至有些题给的是“北”不是“东”。读题时看到起始方向的描述先确认它映射到方向数组的第几个下标。第三坐标起点是0还是1。OD题里两种都有。如果你把0索引的坐标当成1索引去读地图轻则答案错重则直接数组越界。建议在读完坐标后立刻打印一下grid[sx][sy]做验证确认不是障碍物。4.4 常见错误速查表症状可能原因快速修复答案比期望大visited只有二维改成三维visited超时pushLine遇到visited后继续试探遇到visited直接break死循环出队时不判断终点且状态重复入队检查visited是否在入队时立即标记数组越界坐标索引从1开始被当成0读题确认坐标范围从起点无法出发起点格子就是0障碍物读数据后先判断grid[sx][sy]左转方向写错用了(dir-1)%4导致负数用(dir3)%4替代我自己刷这类题时还有一个习惯写完代码先用小规模自测比如3乘3的地图把所有格子的可达性手推一遍然后跟程序输出对照。这种题只要小数据对了大数据基本不会出逻辑问题。5. 同类型题目变形与扩展思路5.1 每个转向都有不同耗时的版本有些题目会把“代价”改得更细比如左转耗时2秒、右转耗时1秒甚至直行在不同路段有不同油耗。这时候“最少转弯次数”就变成了“最小代价路径”普通BFS就不再适用需要升级成Dijkstra或者0-1 BFS。思路其实还是这个思路状态依然是(x, y, dir)但队列里维护的不再是层数而是累计代价。每次状态转移时把方向变化产生的代价加上。0-1 BFS用双端队列代价变化为0的插队头代价变化为1的插队尾Dijkstra则用优先队列。这类题是OD后期压轴题的常见出法。你先把基础版的转弯次数BFS吃透再升级成带权最短路就顺理成章了。5.2 带红绿灯等待时间的交叉口版本再进一步如果地图的某些格子被标记成“红绿灯路口”车到这个格子必须等待若干秒那么你要算的就是最省时间的路线而不是最省转弯次数的路线。这时候转弯次数只是众多代价之一红绿灯等待时间可能更大。搜索状态依然要带方向因为等待时间和方向无关但转弯和直行的代价不同所以还是要维护完整状态。从算法上说这类题就是Dijkstra的教科书场景。你甚至可以自己改一版把原题从“求最少转弯次数”改成“求最短耗时”然后对比两版代码的结构差异这样理解会更深刻。5.3 真实路网与自动驾驶路径规划的关联有人会觉得网格地图离真正的智能驾驶太远。其实不然。很多低速园区无人车、清扫机器人、快递小车的路径规划底层就是把地图栅格化然后在栅格上做搜索。方向、转弯代价、障碍物膨胀这些问题都和我上面讲的状态设计直接相关。区别在于真实场景里硬转弯很伤轮胎也会让乘客不舒服所以转弯惩罚往往比直行大。这和“最少转弯次数”的优化目标本质上是一回事。你理解了网格上的转弯代价再看真实路网上给转弯加权重逻辑是完全一致的。所以别小看这道题它不是一个孤立的算法模板而是把“方向作为状态”这个思路种到你脑子里。以后不管遇到带朝向的机器人、带方向的贪吃蛇、还是路径规划里的航向约束你都能第一时间想到三维状态搜索。我在刷题时一直保留一个习惯把二维网格题的状态列出来确认搜索对象到底是格子本身还是“格子 方向”。这道题如果只背模板换个场景很容易翻车想清楚状态定义同类题基本都能顺手下掉。这道智能驾驶题真正值得记住的不是三份代码而是那个决定正确与否的三维visited。