企业官网建设流程全解析

华为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. 解题思路：为什么是“直行免费、转弯分层”的BFS

2.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版：状态类与ArrayDeque

Java实现里我习惯单独定义一个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]; Queue<State> 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(Queue<State> 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; vector<vector<int>> grid(n, vector<int>(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}; vector<vector<vector<bool>>> visited( n, vector<vector<bool>>(m, vector<bool>(4, false)) ); queue<State> 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++的vector<vector<vector<bool>>>虽然写着麻烦，但安全。如果你确定地图最大不超过100，也可以用bool visited[105][105][4]这种静态数组，性能更好，代码更短，但存在数组越界的风险。

ios::sync_with_stdio(false)和cin.tie(nullptr)这两行建议直接背下来。不加的话，cin在大输入下可能比scanf慢不少，加了之后基本持平。Lambda里用[&]捕获所有外部变量，方便直接访问grid、visited和q。

3.4 三份代码的差异与共性

三份代码其实只有一个pushLine函数的差别，其余骨架完全一样。这里用表格对比一下关键差异，方便你在考场上快速切换语言：

共性是：都按“先直行、再左右转”的顺序扩展；都只在入队时标记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 常见错误速查表

我自己刷这类题时还有一个习惯：写完代码先用小规模自测，比如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。