题解——最少转弯问题

提供三种不同的方法
第一种 DFS方法

#include <iostream>  // 包含输入输出流库，用于cin和cout操作
#include <cstring>   // 包含字符串处理库，用于memset函数初始化数组
using namespace std; // 使用标准命名空间
 
const int MAXN = 105;       // 定义地图最大尺寸，限制地图大小为105x105
const int INF = 0x3f3f3f3f; // 定义无穷大值(约为10^9)，用于初始化距离和比较
const int dx[4] = {-1, 0, 1, 0}; // 方向数组，表示上、右、下、左四个方向的x坐标偏移量
const int dy[4] = {0, 1, 0, -1}; // 方向数组，表示上、右、下、左四个方向的y坐标偏移量
 
int n, m;           // n和m分别表示地图的行数和列数，用于定义地图大小
int x1, y1, x2, y2; // (x1,y1)表示起点坐标，(x2,y2)表示终点坐标
int map[MAXN][MAXN]; // 存储地图信息，0表示空地可以通行，1表示障碍物不可通行
int dist[MAXN][MAXN][4]; // 三维数组，dist[i][j][k]表示到达(i,j)点，方向为k时的最小拐弯次数
int min_turns; // 全局变量，记录到达终点的最小拐弯次数
 
// 判断坐标(x,y)是否有效（在地图范围内且不是障碍物）
bool valid(int x, int y) {
    // 检查坐标是否在地图范围内(1到n和1到m)且该位置是空地(值为0)
    return x >= 1 && x <= n && y >= 1 && y <= m && map[x][y] == 0;
}
 
// DFS函数，用于深度优先搜索最小拐弯路径
void dfs(int x, int y, int dir, int turns) {
    // 如果当前拐弯次数已经大于等于已知的最小拐弯次数，则剪枝（优化搜索）
    if (turns >= min_turns) return;
     
    // 如果当前拐弯次数已经大于已知的到达该位置该方向的最小拐弯次数，则剪枝
    if (turns >= dist[x][y][dir]) return;
     
    // 更新到达当前位置当前方向的最小拐弯次数
    dist[x][y][dir] = turns;
     
    // 到达终点，更新全局最小拐弯次数
    if (x == x2 && y == y2) {
        min_turns = min(min_turns, turns); // 使用min函数更新最小值
        return; // 找到一条路径，返回继续搜索其他可能路径
    }
     
    // 尝试四个方向的移动（上、右、下、左）
    for (int i = 0; i < 4; ++i) {
        int nx = x + dx[i]; // 计算新的x坐标，通过当前坐标加上方向偏移量
        int ny = y + dy[i]; // 计算新的y坐标，通过当前坐标加上方向偏移量
         
        if (!valid(nx, ny)) continue; // 如果新位置无效（超出地图范围或是障碍物），则跳过
         
        // 计算新的拐弯次数
        int new_turns = turns; // 初始化新的拐弯次数为当前拐弯次数
        if (x != x1 || y != y1) { // 如果不是起点（起点可以任意选择方向，不算拐弯）
            if (i != dir) new_turns++; // 如果新方向与当前方向不同，拐弯次数+1
        }
         
        // 递归搜索，继续DFS探索新位置
        dfs(nx, ny, i, new_turns);
    }
}
 
int main() {
    ios::sync_with_stdio(false); // 关闭C和C++的输入输出同步，加速输入输出操作
    cin.tie(0); // 解除cin与cout的绑定，进一步加速输入输出
     
    cin >> n >> m; // 输入地图的行数n和列数m，确定地图大小
    for (int i = 1; i <= n; ++i) { // 遍历地图的每一行
        for (int j = 1; j <= m; ++j) { // 遍历地图的每一列
            cin >> map[i][j]; // 输入地图信息，0表示空地，1表示障碍物
        }
    }
     
    cin >> x1 >> y1 >> x2 >> y2; // 输入起点坐标(x1,y1)和终点坐标(x2,y2)
     
    // 初始化距离数组和最小拐弯次数
    memset(dist, 0x3f, sizeof(dist)); // 将dist数组所有元素初始化为INF
    min_turns = INF; // 初始化全局最小拐弯次数为无穷大
     
    // 从四个方向开始DFS，尝试所有可能的起始方向
    for (int i = 0; i < 4; ++i) {
        dfs(x1, y1, i, 0); // 从起点(x1,y1)开始，方向为i，初始拐弯次数为0
    }
     
    // 输出结果
    if (min_turns == INF) { // 如果最小拐弯次数仍为INF，说明无法到达终点
        cout << -1 << endl; // 输出-1表示无解
    } else {
        cout << min_turns << endl; // 输出最小拐弯次数
    }
     
    return 0; // 程序正常结束，返回0表示成功执行
}

第二种 BFS方法

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
 
const int MAXN = 105;
const int INF = 0x3f3f3f3f;
const int dx[4] = {-1, 0, 1, 0}; // 上、右、下、左
const int dy[4] = {0, 1, 0, -1};
 
int n, m;
int x1, y1, x2, y2;
int map[MAXN][MAXN];
int dist[MAXN][MAXN][4]; // dist[i][j][k]表示到达(i,j)点，方向为k时的最小拐弯次数
 
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 valid(int x, int y) {
    return x >= 1 && x <= n && y >= 1 && y <= m && map[x][y] == 0;
}
 
int bfs() {
    memset(dist, 0x3f, sizeof(dist));
    queue<Node> q;
     
    // 初始位置可以从四个方向出发，拐弯次数都是0
    for (int i = 0; i < 4; ++i) {
        dist[x1][y1][i] = 0;
        q.push(Node(x1, y1, i, 0));
    }
     
    int min_turns = INF;
     
    while (!q.empty()) {
        Node cur = q.front();
        q.pop();
         
        int x = cur.x, y = cur.y, dir = cur.dir, turns = cur.turns;
         
        // 如果当前拐弯次数已经大于已知的最小拐弯次数，则跳过
        if (turns > dist[x][y][dir]) continue;
         
        // 到达终点，更新最小拐弯次数
        if (x == x2 && y == y2) {
            min_turns = min(min_turns, turns);
            continue;
        }
         
        // 尝试四个方向
        for (int i = 0; i < 4; ++i) {
            int nx = x + dx[i];
            int ny = y + dy[i];
             
            if (!valid(nx, ny)) continue;
             
            // 计算新的拐弯次数
            int new_turns = turns;
            if (x != x1 || y != y1) { // 不是起点
                if (i != dir) new_turns++; // 改变方向，拐弯次数+1
            }
             
            if (new_turns < dist[nx][ny][i]) {
                dist[nx][ny][i] = new_turns;
                q.push(Node(nx, ny, i, new_turns));
            }
        }
    }
     
    return min_turns == INF ? -1 : min_turns;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
     
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> map[i][j];
        }
    }
     
    cin >> x1 >> y1 >> x2 >> y2;
     
    int ans = bfs();
    cout << ans << endl;
     
    return 0;
}

第三种

#include<bits/stdc++.h>
using namespace std;
const int dx[]={0,1,0,-1};
const int dy[]={1,0,-1,0};
struct sj{
int x,y,turn;
}s,t,p;
queue<sj> q;
int n,m,c[101][101];
bool v[101][101];
int main()
{
 
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    scanf("%d",&c[i][j]);
    scanf("%d%d%d%d",&s.x,&s.y,&t.x,&t.y);
    q.push(s);
    memset(v,0,sizeof(v));
    q.front().turn=0;
        while(!q.empty())
        {
            for(int i=0;i<4;i++)
            {
                p.x=q.front().x+dx[i];
                p.y=q.front().y+dy[i];
                while(p.x>0&&p.x<=n&&p.y>0&&p.y<=m&&!c[p.x][p.y])
                {
                    if(!v[p.x][p.y])
                    {
                        if(p.x==t.x&&p.y==t.y)
                        {
                            printf("%d\n",q.front().turn);
                            return 0;
                        }
                        v[p.x][p.y]=1;
                        p.turn=q.front().turn+1;
                      
                        q.push(p);
                    }
                    
                    p.x+=dx[i];
                    p.y+=dy[i];
                }
            }
            q.pop();
        }
}

希望对大家有帮助！！！
最后一种方法不想写注释啦