问题描述 农夫约翰在农场工作了一天，感觉比较累，准备开车回家。约翰在比较累的时候，喜欢走直路，不喜欢拐弯，哪怕走少拐弯的路回家更远，约翰也想走直路（好任性的约翰!）。请你从约翰的出发地到目的地找一条路，使得约翰回家拐弯数量最少。 输入格式 第一行两个整数 � n 和 � m（ � n 和 � m 都是 1000 1000 以内的整数），代表地图的大小。 接下来的 � n 行，每行有 � m 个数，其中能够通行的点用 0 0 表示，不能通行的点用 1 1 表示。 再接下来 1 1 行，有 4 4 个整数， � 1 s 1 ​ 、 � 2 s 2 ​ 、 � 1 e 1 ​ 、 � 2 e 2 ​ ， � 1 s 1 ​ 和 � 2 s 2 ​ 表示出发点的坐标， � 1 e 1 ​ 和 � 2 e 2 ​ 表示目的地的坐标。（本题测试数据保证起点和终点不是同一个点，且起点和终点一定可以走） 输出格式 约翰从出发点到目的地最少要拐弯的数量，本题所有数据都确认从出发点到目的地是有路径可达的。 样例 输入 #1 5 7 1 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 1 1 0 0 0 0 0 0 0 0 1 1 0 1 3 1 7 输出 #1 5 输入 #2 2 3 0 0 1 0 0 0 1 1 2 3 输出 #2 1用c++解决

好的，用户想用C++实现一个算法，找到从起点到终点路径中拐弯次数最少的解法。首先，我得理解这个问题。最小拐弯路径问题，核心是在网格地图中找到一条路径，使得转弯的次数最少。这通常用在机器人导航或者游戏AI中，减少不必要的转向可以优化移动效率。
用户提到的地图大小、障碍物分布和起终点位置，这些都是输入条件。我需要考虑如何表示地图，如何处理障碍物，以及如何高效地搜索路径。常规的BFS可能不太适用，因为BFS一般是找最短路径（步数最少），而这里需要的是转弯次数最少。所以需要调整搜索策略，优先考虑转弯次数少的路径。
接下来，我应该想到使用广度优先搜索（BFS）的变种，或者优先级队列（比如Dijkstra算法）。因为每次转弯可以视为一种权重，不过这里需要最小化转弯次数，所以可能需要记录到达每个点的最少转弯次数，并优先处理转弯次数少的节点。
然后，数据结构方面，每个节点可能需要保存当前位置、方向、已转弯次数。方向很重要，因为每次移动如果方向改变，就增加转弯次数。比如，从向上变成向右，就是一次转弯。所以需要记录当前移动的方向，以便判断下一次移动是否转弯。
另外，需要避免重复访问同一节点时，之前已经有更优（更少转弯次数）的路径到达过。因此，维护一个二维数组或者哈希表来记录每个位置在各个方向上的最小转弯次数，如果新的路径到达同一位置同一方向时转弯次数更多或相等，就可以剪枝，不需要继续处理。
然后，障碍物的处理比较简单，在移动时需要检查目标位置是否为障碍物或者超出地图范围。
可能的步骤包括：

定义方向：上下左右四个方向，或者八个方向（如果允许斜向移动，但通常可能只允许四方向）。
初始化队列，起点可以朝四个方向开始，但初始方向可能需要特殊处理，比如起始时尚未移动，所以第一次移动不算转弯。
在BFS过程中，每次从队列中取出一个节点，然后尝试向四个方向移动。如果方向改变，则转弯次数+1，否则不变。
对于每个新位置，检查是否已经存在更优的记录，如果当前转弯次数更少，则更新记录，并将该节点加入队列。
当到达终点时，记录最小的转弯次数。

需要注意的是，起点本身可能没有方向，所以第一次移动的方向应该不算转弯。例如，从起点出发，向任意方向移动都是第一次，转弯次数为0。之后每次改变方向才会增加次数。
现在，如何具体实现呢？比如，用结构体或类来保存每个节点的信息：坐标(x,y)、当前方向、已转弯次数。或者，可以将方向分开处理，比如使用一个三维的访问数组，记录每个坐标和方向的最小转弯次数。
例如，访问数组可以是一个三维数组visited[x][y][dir]，存储到达(x,y)时方向为dir的最小转弯次数。这样，当处理某个节点时，如果新的转弯次数小于已存储的值，才继续处理。
接下来，代码结构大致如下：

定义方向数组，表示上下左右的dx和dy。
使用队列来进行BFS，队列元素包括坐标、方向、转弯次数。
初始化时，可能需要将起点的四个方向都加入队列，转弯次数为0，因为初始移动不算转弯？
或者，起点没有方向，所以第一次移动的任何方向都不算转弯，之后的方向改变才算。

这个问题可能需要特别处理起点的情况。例如，起点的初始方向可以设为-1或者某个特殊值，表示还未移动。当第一次移动时，无论哪个方向都不算转弯，因为这是初始方向。之后的移动如果改变方向就算一次转弯。
例如，初始时，起点位置，方向为无，转弯次数为0。然后，对于每个可能的初始移动方向，将它们加入队列，转弯次数为0。之后的每次移动，如果方向改变，则次数+1，否则保持。
所以，BFS的初始状态可能需要处理起点周围的四个方向，每个方向作为初始移动，转弯次数0。然后，从这些方向开始扩展。
举个例子，起点是(0,0)，终点是(5,5)。第一次移动可以是上、下、左、右，每个方向对应的转弯次数都是0。比如，向右走到(0,1)，此时方向是右，转弯次数0。接下来，如果继续向右，转弯次数不变；如果向上或者向下，转弯次数+1。
这样，每个节点的状态需要包括位置、当前方向、已转弯次数。在访问数组里，需要记录每个位置在每个方向下的最小转弯次数。如果新的路径到达同一位置同一方向时的转弯次数更小，才需要处理。
这样，当处理一个节点时，遍历四个方向，计算新的转弯次数。例如，当前方向是右，下一步如果继续右，转弯次数不变；如果转向上或下，转弯次数+1；转向左则不可能，因为是反方向？
或者，是否允许掉头？比如，原本向右，现在向左，这应该算一次转弯。需要根据问题定义是否允许这样的移动。通常，在网格中移动，可能允许掉头，但这样会导致转弯次数增加。
现在，代码的大致流程：

输入地图大小、障碍物位置、起点和终点坐标。
初始化一个三维数组visited[x][y][dir]，记录每个位置在每个方向上的最小转弯次数，初始为无穷大。
将起点周围四个方向的可能移动加入队列，每个方向的转弯次数为0（因为初始移动不算转弯），前提是移动后的位置不是障碍物且在地图内。
使用队列进行BFS，每次取出一个节点。
对于当前节点的每个可能方向，计算新的位置，检查是否越界或障碍物。
计算新的转弯次数：如果方向与当前方向不同，则转弯次数+1；否则保持。
如果新的转弯次数小于visited中记录的值，则更新visited，并将该节点加入队列。
当到达终点时，记录最小的转弯次数。

但这里有个问题：在起点的时候，初始方向如何处理？比如，起点是（sx, sy），第一次移动的方向可以是四个方向中的任何一个，此时转弯次数为0，因为还没有转弯。例如，假设初始方向是NONE，第一次移动的方向是右，那么转弯次数为0。之后，如果改变方向，比如向上，那么次数增加到1。
或者，在起点时，第一次移动的方向不计入转弯次数，因为还没有方向。所以，当从起点出发，无论哪个方向都是初始方向，之后每次改变方向都算一次转弯。
这可能需要将初始方向设为特殊值，比如-1，然后第一次移动的方向不计入转弯次数。例如：
起点（sx, sy）的方向是-1，此时尝试四个方向移动。对于每个方向，新的方向是该方向，转弯次数是0？或者是否是0？比如，初始方向不存在，所以第一次移动的方向不算转弯。例如，从起点到第一个点，无论向哪个方向移动，都视为第一次移动，转弯次数0。然后，从第一个点移动时，如果方向改变，则次数+1。
所以，初始节点的处理可能需要特殊处理。例如，初始节点的方向是-1，此时移动后的方向是新的方向，转弯次数为0。之后，每个移动如果方向改变，则次数+1。
例如，起点的队列元素是（sx, sy，方向-1，转弯次数-1？或者0？）。这可能需要调整逻辑。
或者，另一种处理方式是，起点的初始移动可以是四个方向中的任意一个，转弯次数为0。因为第一次移动不算转弯。然后，之后的移动如果方向改变，次数增加。
例如，初始队列中添加四个可能的移动方向，每个方向对应的转弯次数为0。例如，起点（sx, sy）的下一个位置可以是四个方向的可行位置，每个方向的转弯次数为0。然后，在处理这些节点时，移动方向是当前的移动方向，之后的移动如果改变方向，则次数+1。
例如：
struct Node {
int x, y;
int dir; // 当前移动方向，0-3对应上下左右
int turns; // 已转弯次数
};
初始化时，将起点周围的四个可行方向的位置加入队列，每个的turns为0。如果起点周围的某个方向的位置不可达（比如障碍物或出界），则跳过。
这样，在BFS过程中，每次从队列中取出节点，然后尝试四个方向。对于每个新方向：

如果新方向等于当前节点的dir，则转弯次数不变。
否则，转弯次数+1。

但这样有个问题：比如，当前方向是右，新的方向是左，是否算转弯？这取决于问题定义是否允许掉头。如果允许，那么算一次转弯。否则可能需要禁止掉头，但这通常不是限制，所以应该允许，视为一次转弯。
所以，每次移动时，只要方向改变，不管转向哪个方向，都算一次转弯。
因此，在BFS过程中，对于每个可能的移动方向，计算新的转弯次数，并检查是否更优。
现在，如何实现这个逻辑？
可能的代码结构：
定义四个方向：上、下、左、右，用0,1,2,3表示。dx和dy数组对应每个方向的移动。
当处理节点（x,y,dir,turns）时，遍历四个可能的new_dir：
对于每个new_dir，计算新位置nx = x + dx[new_dir]，ny = y + dy[new_dir]。
检查nx和ny是否在地图范围内，且不是障碍物。
如果合法，则计算new_turns：
如果当前节点的dir是初始方向（比如初始是-1，表示起点），则new_turns = turns（因为第一次移动不算转弯）。或者，当dir是初始值时，第一次移动的方向new_dir，无论是什么，都算转弯次数0？
这可能需要特别处理起点的初始状态。例如，起点的初始dir为-1，当处理初始节点时，new_dir的转弯次数为0，因为这是第一次移动。然后，之后的移动，如果new_dir与当前dir不同，则new_turns = turns + 1，否则new_turns = turns.
所以，初始队列中的元素是起点的四个方向的可能移动，每个的dir为对应的方向，turns为0。比如，起点（sx, sy），尝试向上移动，则新位置是（sx-1, sy），dir=0，turns=0。如果该位置合法，则加入队列。
然后，处理队列中的节点时，比如当前节点是（x,y,dir,turns），尝试四个new_dir：
如果 new_dir == dir → new_turns = turns.
否则 → new_turns = turns +1.
然后，比较这个新位置和new_dir下的已记录的最小转弯次数。如果new_turns更小，则更新并加入队列。
这样，就能保证找到转弯次数最少的路径。
此外，当到达终点时，可能需要记录所有可能的路径中的最小转弯次数，或者一旦到达终点就可以立即返回，因为BFS的特性，先到达的转弯次数最少？
不过，由于BFS是按照转弯次数逐层扩展的，所以当第一次到达终点时，此时的转弯次数就是最小的。所以可以在找到终点时立即返回结果。
但可能需要注意，队列的处理方式是否是按转弯次数递增的顺序处理。例如，使用优先队列，按转弯次数排序，或者使用普通队列，因为每次增加的转弯次数最多是1，所以普通队列可以保证按层处理。
不过，普通的BFS队列可能无法保证，因为同一层可能有不同转弯次数。例如，可能存在一个节点转弯次数为2，而另一个节点转弯次数为1的情况同时存在于队列中。所以可能需要使用优先队列（即Dijkstra算法），其中优先级是转弯次数，这样每次处理转弯次数最少的节点，保证找到最优解。
或者，修改BFS的方式，将相同转弯次数的节点一起处理，类似于层次遍历。但可能比较复杂，所以更可靠的方式是使用优先队列，每次取出转弯次数最少的节点进行处理，这样能确保一旦到达终点，就是最少转弯次数。
因此，可能更适合使用优先队列（即Dijkstra算法）来处理这个问题，因为不同的路径可能有不同的转弯次数，而优先队列可以保证优先处理转弯次数少的节点。
不过，在Dijkstra算法中，每个节点的状态需要记录转弯次数，并且需要维护一个优先级队列，按转弯次数从小到大排列。这样，当处理到终点时，可以立即返回结果。
因此，算法的大致步骤：

定义四个方向及其对应的dx, dy数组。
读取输入地图，起点和终点。
初始化一个三维数组visited[x][y][dir]，记录到达(x,y)时方向为dir的最小转弯次数，初始为无穷大。
使用优先队列（堆），按转弯次数从小到大排列。
对于起点，尝试四个可能的初始方向，检查是否可行（即移动后的位置不是障碍物，且在地图内）。如果可行，将这些初始方向对应的节点加入队列，转弯次数为0，并更新visited数组。
如果起点和终点相同，直接返回0。
否则，开始处理队列中的节点：
a. 取出转弯次数最少的节点（x,y,dir,turns）。
b. 如果（x,y）是终点，返回turns。
c. 否则，遍历四个可能的new_dir。
d. 计算新位置nx = x + dx[new_dir], ny = y + dy[new_dir].
e. 检查新位置是否合法。
f. 计算new_turns：如果当前dir是初始的-1（表示起点），则new_turns = turns（0） + (是否改变方向？如果起点初始方向是-1，那么第一次移动的new_dir无论是什么，new_turns都是0？或者是否需要处理？
g. 这里可能需要重新考虑起点的情况。假设起点的初始dir是特殊值，比如-1，此时第一次移动的new_dir无论是什么，都视为不转弯，所以new_turns=0。但是这可能与之后的情况混淆。或者，在初始化队列时，起点的每个可能移动的dir是具体方向，turns为0。这样，后续的处理中，new_dir的变化是基于当前节点的dir。

例如，在初始化时，起点的周围四个可行方向被加入队列，每个的turns为0。例如，起点是（sx,sy），如果向上移动可行，则加入队列的节点是（sx-1, sy, 上方向，0）。这样，在处理这个节点时，下一步如果继续向上，则turns保持0；如果转其他方向，则turns变为1。
这样，后续的处理中，每个节点的dir是明确的方向，所以计算new_turns的时候只需要比较new_dir和当前节点的dir是否相同。
因此，在代码中，当处理一个节点（x,y,dir,turns）时：
对于每个new_dir in 0-3:
new_turns = turns + (new_dir != dir ? 1 : 0);
但是，当dir是初始方向时，比如在起点周围加入的节点，此时dir已经是具体的某个方向，所以计算new_turns时，如果new_dir与dir不同，则turns+1。例如，初始移动的方向是上，那么下一步如果转左，turns+1=1。
这样，在初始化时，起点的每个可行方向的移动都被视为初始移动，turns为0。例如，起点移动到右边，此时turns是0。如果下一步继续右，turns还是0；如果转向上或下，turns变为1。
这样，代码逻辑就统一了，无需特殊处理起点的情况，除了初始化时将四个方向的可行移动加入队列。
现在，关于visited数组，每个位置（x,y）的每个方向dir都需要记录最小的转弯次数。如果某个新的路径到达同一位置同一方向，但转弯次数更小，则需要更新。
例如，当从某个方向到达（x,y）时，如果该方向的visited[x][y][dir]的值比当前new_turns大，则更新，并将该节点加入队列。
综上，代码的大致结构如下：

定义四个方向，比如：
const int dx[] = {-1, 1, 0, 0}; // 上、下、左、右
const int dy[] = {0, 0, -1, 1};

使用优先队列，存储结构体包含x, y, dir, turns，按turns从小到大排序。

初始化时，检查起点的四个方向移动是否可行，若可行，将对应的节点加入队列，并设置visited[sx][sy][dir] = 0。

处理队列中的每个节点，直到队列为空或找到终点。

另外，需要注意，起点可能被障碍物包围，导致无法到达终点，此时需要返回-1或其他错误标识。
现在，代码的具体实现：
假设地图用二维数组grid表示，其中grid[x][y]为1表示障碍物，0表示可通行。起点为（sx, sy），终点为（ex, ey）。
结构体可能如下：
struct Node {
int x, y, dir, turns;
Node(int x, int y, int dir, int turns) : x(x), y(y), dir(dir), turns(turns) {}
bool operator<(const Node& other) const {
return turns > other.turns; // 小顶堆，按turns升序排列
}
};
然后，初始化队列时，需要将起点的四个方向可行的移动加入：
for (int i = 0; i < 4; ++i) {
int nx = sx + dx[i];
int ny = sy + dy[i];
if (nx >=0 && nx < rows && ny >=0 && ny < cols && grid[nx][ny] == 0) {
if (nx == ex && ny == ey) { // 直接到达终点
return 0;
}
visited[nx][ny][i] = 0;
pq.push(Node(nx, ny, i, 0));
}
}
然后，处理队列中的每个节点：
while (!pq.empty()) {
Node curr = pq.top();
pq.pop();
if (curr.x == ex && curr.y == ey) {
return curr.turns;
}
for (int i = 0; i < 4; ++i) {
int nx = curr.x + dx[i];
int ny = curr.y + dy[i];
if (nx <0 || nx >= rows || ny <0 || ny >= cols || grid[nx][ny] == 1) {
continue;
}
int new_turns = curr.turns + (i != curr.dir ? 1 : 0);
if (new_turns < visited[nx][ny][i]) {
visited[nx][ny][i] = new_turns;
pq.push(Node(nx, ny, i, new_turns));
}
}
}
但这里有个问题：visited数组是三维的，对于较大的地图，可能导致内存问题。例如，如果地图是1000x1000，四个方向，则visited需要100010004的空间，这大约是4,000,000，对于C++来说可能没问题，但需要考虑优化。
不过，在题目中，用户可能只是需要解决一般规模的问题，所以这个结构是可行的。
此外，当处理到终点时，需要立即返回curr.turns，因为优先队列保证最先到达终点的是转弯次数最少的。
但有可能存在多条路径到达终点，而优先队列会优先处理转弯次数最少的，因此一旦找到终点即可返回结果。
现在，如何处理起点和终点是同一个点的情况？此时，转弯次数为0，但可能需要根据问题要求处理。比如，如果起点等于终点，返回0。
另外，在初始化时，如果起点周围的四个方向都无法移动，说明起点被障碍物包围，无法到达任何地方，包括终点，此时返回-1。
此外，在代码中，visited数组需要初始化为无穷大，可以用INT_MAX或者某个大数。在C++中，可以用memset或循环初始化。
综上，完整的C++代码可能如下：
#include
#include
#include
#include
using namespace std;
struct Node {
int x, y, dir, turns;
Node(int x, int y, int dir, int turns) : x(x), y(y), dir(dir), turns(turns) {}
bool operator<(const Node& other) const {
return turns > other.turns; // 小顶堆，按turns升序排列
}
};
const int dx[] = {-1, 1, 0, 0}; // 上、下、左、右
const int dy[] = {0, 0, -1, 1};
int min_turn_path(vector<vector>& grid, int sx, int sy, int ex, int ey) {
int rows = grid.size();
if (rows == 0) return -1;
int cols = grid[0].size();
if (sx == ex && sy == ey) return 0; // 起点终点重合
vector<vector<vector<int>>> visited(rows, vector<vector<int>>(cols, vector<int>(4, INT_MAX)));
priority_queue<Node> pq;

// 初始化四个方向
for (int i = 0; i < 4; ++i) {
int nx = sx + dx[i];
int ny = sy + dy[i];
if (nx >=0 &amp;&amp; nx < rows &amp;&amp; ny >=0 &amp;&amp; ny < cols &amp;&amp; grid[nx][ny] == 0) {
if (nx == ex &amp;&amp; ny == ey) return 0; // 一步到达终点
visited[nx][ny][i] = 0;
pq.push(Node(nx, ny, i, 0));
}
}

while (!pq.empty()) {
Node curr = pq.top();
pq.pop();

if (curr.x == ex &amp;&amp; curr.y == ey) {
return curr.turns;
}

// 剪枝：如果当前turns已经大于等于已记录的最小值，跳过
if (curr.turns > visited[curr.x][curr.y][curr.dir]) {
continue;
}

for (int i = 0; i < 4; ++i) {
int nx = curr.x + dx[i];
int ny = curr.y + dy[i];
if (nx <0 || nx >= rows || ny <0 || ny >= cols || grid[nx][ny] == 1) {
continue;
}

int new_turns = curr.turns + (i != curr.dir ? 1 : 0);
if (new_turns < visited[nx][ny][i]) {
visited[nx][ny][i] = new_turns;
pq.push(Node(nx, ny, i, new_turns));
}
}
}

return -1; // 无法到达
登录后复制
}
int main() {
// 示例输入
int rows = 5, cols = 5;
vector<vector> grid = {
{0,0,0,0,0},
{0,1,1,0,0},
{0,1,0,0,0},
{0,1,0,1,0},
{0,0,0,0,0}
};
int sx = 0, sy = 0;
int ex = 4, ey = 4;
int result = min_turn_path(grid, sx, sy, ex, ey);
cout << "Minimum turns: " << result << endl;
return 0;
登录后复制
}
这个代码示例中，使用优先队列来处理节点，并维护一个三维的visited数组记录每个位置每个方向的最小转弯次数。每次处理节点时，尝试四个方向，并计算新的转弯次数。如果新路径更优，则更新visited并加入队列。当到达终点时，返回转弯次数。
需要注意的是，剪枝操作：如果当前节点的turns已经大于visited中存储的值，说明之前已经有更优的路径到达该节点，所以跳过处理。这可以避免重复处理无效的路径，提高效率，类似Dijkstra算法的处理方式。
在引用中，用户提供的参考内容中提到剪枝操作，如果当前路径的转弯次数已经大于等于已记录的最优值，则剪枝。这在这个代码中的剪枝步骤也体现了这一点。
例如，参考引用[3]提到：如果当前路径的转弯次数大于等于已记录的最小值，则直接返回，避免不必要的计算。在这个代码中，当从队列取出节点时，如果curr.turns > visited[curr.x][curr.y][curr.dir]，则跳过处理，因为已经有更优的路径到达该节点的该方向。
综上，这个代码应该能够有效地解决最小拐弯路径问题。要解决最小拐弯路径问题，可以使用改进的广度优先搜索（BFS）或Dijkstra算法，通过优先处理转弯次数少的路径来优化搜索效率。以下是具体实现步骤：

实现思路

方向定义定义四个移动方向（上、下、左、右），用方向向量表示：
const int dx[] = {-1, 1, 0, 0}; // 上下左右
const int dy[] = {0, 0, -1, 1};
登录后复制

状态表示每个节点包含坐标$(x,y)$、当前方向dir和已转弯次数turns。使用优先队列按turns从小到大排序，确保优先处理转弯少的路径。

剪枝优化维护三维数组visited[x][y][dir]，记录到达位置$(x,y)$时方向为dir的最小转弯次数。若新路径的turns更大，则跳过该路径[^3]。

终止条件当首次到达终点时，当前turns即为最小值（优先队列保证最先找到最优解）。

C++代码实现
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

struct Node {
int x, y, dir, turns;
Node(int x, int y, int dir, int turns) : x(x), y(y), dir(dir), turns(turns) {}
bool operator<(const Node&amp; other) const {
return turns > other.turns; // 小顶堆，按turns升序
}
};

const int dx[] = {-1, 1, 0, 0}; // 上、下、左、右
const int dy[] = {0, 0, -1, 1};

int minTurnPath(vector<vector<int>>&amp; grid, int sx, int sy, int ex, int ey) {
int rows = grid.size();
if (rows == 0) return -1;
int cols = grid[0].size();
if (sx == ex &amp;&amp; sy == ey) return 0;

// visited[x][y][dir] 记录最小转弯次数
vector<vector<vector<int>>> visited(rows,
vector<vector<int>>(cols, vector<int>(4, INT_MAX)));
priority_queue<Node> pq;

// 初始化起点的四个方向
for (int dir = 0; dir < 4; dir++) {
int nx = sx + dx[dir], ny = sy + dy[dir];
if (nx >= 0 &amp;&amp; nx < rows &amp;&amp; ny >= 0 &amp;&amp; ny < cols &amp;&amp; !grid[nx][ny]) {
if (nx == ex &amp;&amp; ny == ey) return 0;
visited[nx][ny][dir] = 0;
pq.push(Node(nx, ny, dir, 0));
}
}

while (!pq.empty()) {
Node curr = pq.top();
pq.pop();

if (curr.x == ex &amp;&amp; curr.y == ey) return curr.turns;
if (curr.turns > visited[curr.x][curr.y][curr.dir]) continue; // 剪枝

for (int new_dir = 0; new_dir < 4; new_dir++) {
int nx = curr.x + dx[new_dir], ny = curr.y + dy[new_dir];
if (nx < 0 || nx >= rows || ny < 0 || ny >= cols || grid[nx][ny])
continue;

int new_turns = curr.turns + (new_dir != curr.dir ? 1 : 0);
if (new_turns < visited[nx][ny][new_dir]) {
visited[nx][ny][new_dir] = new_turns;
pq.push(Node(nx, ny, new_dir, new_turns));
}
}
}
return -1; // 不可达
}

int main() {
vector<vector<int>> grid = {
{0,0,0,0,0},
{0,1,1,0,0},
{0,1,0,0,0},
{0,1,0,1,0},
{0,0,0,0,0}
};
cout << "Minimum turns: " << minTurnPath(grid, 0, 0, 4, 4) << endl;
return 0;
}
登录后复制

代码说明

方向处理起点尝试向四个方向移动，每个方向初始turns=0，因为首次移动不算转弯。
剪枝逻辑若当前路径的转弯次数已大于历史记录，直接跳过，避免无效计算[^3]。
终点判断首次到达终点时直接返回结果，优先队列保证此时turns最小。

相关优化问题

如何应对大规模地图？可使用双向BFS或A*算法，结合启发式函数进一步优化搜索效率。
如何处理动态障碍物？需实时更新grid数组，并在状态中引入时间维度。
如何记录具体路径？添加父节点指针，通过回溯生成完整路径（参考路径回溯方法[^4]）。