迷宫两点间最小转弯路径求解：Dijkstra实现结果非最优问题排查

给定由0和1组成的2D矩阵，仅可在值为1的位置移动，从起点(x,y)出发，可向上下左右4个相邻方向移动，对应坐标为(x+1, y)、(x-1, y)、(x, y+1)、(x, y-1)。要求找到从起点(x,y)到终点(s,t)的转弯次数最少的路径。

你当前的实现存在状态维度缺失的问题：turns数组仅记录了到达每个坐标的最小转弯次数，没有记录到达该坐标时的移动方向。同个坐标可以通过不同方向抵达，即便两次抵达的转弯次数相同，不同的入方向也会对后续移动的转弯成本产生影响，仅按坐标去重会丢失可能得到更优解的合法状态，最终导致部分用例无法得到最优解。

举个简单例子：到达坐标(2,2)时存在两个有效状态：

• 状态1：从上方移动到(2,2)，方向向下，转弯次数2
• 状态2：从左侧移动到(2,2)，方向向右，转弯次数2
  你当前的逻辑会把后到的状态2直接过滤掉，但如果后续终点在(2,5)，状态2只需要再直走3步不用额外转弯，状态1则需要先转一次弯再走，此时就会丢失最优解。

将状态维度扩展为三维turns[x][y][d]，d为0~3对应四个移动方向，额外处理起点无初始方向的特殊情况，保证所有合法状态都能被正确判断。

修正后的核心代码参考：

pair<int,int> go[4] = {{-1,0}, {0,1}, {1,0}, {0,-1}};
const int INF = 0x3f3f3f3f;
int turns[105][105][4]; // 按实际矩阵大小调整维度，turns[x][y][d]表示到达(x,y)且方向为d的最小转弯次数

bool minimize(int &x, const int &y){
    if(x > y){
        x = y;
        return true;
    }
    return false;
}

struct Node{
    pair<int,int> point;
    int turn, direc;

    Node(pii _point, int _turn, int _direc){
        point = _point;
        turn = _turn;
        direc = _direc;
    }

    bool operator < (const Node &x) const{
        return turn > x.turn;
    }
};

void dijkstra(){
    memset(turns, 0x3f, sizeof turns);
    priority_queue<Node> pq;
    // 起点初始化，四个方向都可以走，首次移动转弯次数为0
    for(int i=0;i<4;i++){
        int nx = xHome + go[i].first;
        int ny = yHome + go[i].second;
        if(nx>=1 && nx<=row && ny>=1 && ny<=col && matrix[nx][ny]){
            turns[nx][ny][i] = 0;
            pq.push(Node({nx, ny}, 0, i));
        }
    }

    while(!pq.empty()){
        Node cur = pq.top();
        pq.pop();
        pii point = cur.point;
        int direc = cur.direc;
        int cur_turn = cur.turn;
        
        if(cur_turn > turns[point.first][point.second][direc]) continue;

        for(int i = 0; i < 4; i++){
            int x = point.first + go[i].first;
            int y = point.second + go[i].second;
            if(x<1 || x > row || y<1 || y > col) continue;
            if(matrix[x][y]){
                int new_turn = cur_turn + (i != direc);
                if(minimize(turns[x][y][i], new_turn))
                    pq.push(Node({x, y}, new_turn, i));
            }
        }
    }
    // 最终答案是turns[s][t][0~3]四个值中的最小值
}

• 如果你要保留起点转弯次数初始为-1的写法也可以，只要给状态加上方向维度即可解决核心问题
• 得到所有方向到达终点的转弯次数后，取最小值即为所求的最少转弯次数

内容的提问来源于stack exchange，提问作者unglinh279