题解【最少转弯问题】

有代码 有解析 求赞！！！

#include <bits/stdc++.h>
using namespace std;
const int N = 105;
int n, m;
int a[N][N];          // 地图，0 平地，1 高山
int sx, sy, ex, ey;   // 起点、终点
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
int dis[N][N][4];     // 到 (x,y) 且方向为 d 的最少转弯次数
struct node
{
    int x, y, dir;
};
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cin >> a[i][j];
        }
    }
    cin >> sx >> sy >> ex >> ey;
    // 初始化距离为无穷大
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            for (int k = 0; k < 4; k++)
            {
                dis[i][j][k] = 1e9;
            }
        }
    }
    deque<node> q;   // 0-1 BFS
    // 起点可以朝任意方向出发，转弯次数为 0
    for (int d = 0; d < 4; d++)
    {
        dis[sx][sy][d] = 0;
        q.push_back({sx, sy, d});
    }
    while (!q.empty())
    {
        node cur = q.front();
        q.pop_front();
        int x = cur.x, y = cur.y, d = cur.dir;
        // 1. 直走：沿当前方向走一步，转弯次数不变（边权 0）
        int nx = x + dx[d], ny = y + dy[d];
        if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && a[nx][ny] == 0)
        {
            if (dis[nx][ny][d] > dis[x][y][d])
            {
                dis[nx][ny][d] = dis[x][y][d];
                q.push_front({nx, ny, d});   // 0 边权放队首
            }
        }
        // 2. 转弯：改变方向，转弯次数 +1（边权 1）
        for (int nd = 0; nd < 4; nd++)
        {
            if (nd == d) continue;
            if (dis[x][y][nd] > dis[x][y][d] + 1)
            {
                dis[x][y][nd] = dis[x][y][d] + 1;
                q.push_back({x, y, nd});     // 1 边权放队尾
            }
        }
    }
    int ans = 1e9;
    for (int d = 0; d < 4; d++)
    {
        ans = min(ans, dis[ex][ey][d]);
    }
    if (ans == 1e9) cout << "Unattainable";
    else cout << ans;
    return 0;
}