在迷宫中找到两点之间的最小转弯路径

Question

问题：

给定一个由0和1组成的二维矩阵，你只能定位到1。从点(x,y)开始，我们可以移动到4个相邻的点：上、下、左、右；它们是：(x+1, y), (x-1, y), (x, y+1), (x, y-1).

找到一条从点 (x, y) 到点 (s, t) 的路径，使其转弯数最少。

我的问题：

我尝试使用 dijsktra 解决这个问题，它在大多数情况下都是正确的，但在某些情况下，它没有给出最佳答案。

这是我的代码：

pair<int,int> go[4] = {{-1,0}, {0,1}, {1,0}, {0,-1}};

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);
    turns[xHome][yHome] = -1;

    priority_queue<Node> pq;
    pq.push(Node({xHome, yHome}, -1, -1));

    while(!pq.empty()){
        while(!pq.empty() &&
              pq.top().turn > turns[pq.top().point.first][pq.top().point.second])pq.pop();
        if(pq.empty())break;

        pii point = pq.top().point;
        int direc = pq.top().direc;
        pq.pop();

        for(int i = 0; i < 4; i++){
            int x = point.first + go[i].first ;
            int y = point.second + go[i].second;
            if(!x || x > row || !y || y > col)continue;
            if(matrix[x][y])
                if(minimize(turns[x][y], turns[point.first ][point.second] + (i != direc)))
                    pq.push(Node({x, y}, turns[x][y], i));
        }
    }
}

P/S: 主要解决在void dijkstra，其他只是提供一些信息，以备不时之需。

Answer 1

你算法中的一个明显错误是要检测路径的长度 start->x->y，你应该存储所有到 x 的方向，这些方向可以形成从start 到 x.

例如，假设start=(0,0),x=(1,1),y=(1,2)，从start到x有两条路径：start->(0,1)->x、start->(1,0)->x，两者的长度都是最短的。但是，start->(0,1)->x->y有两圈，而start->(1,0)->x->y只有一圈。所以你需要存储每个节点的所有方向（在这种情况下，你应该将方向 (0,1)->x 和 (1,0)->x 存储在 x.

Answer 2

我找到了解决这个问题的方法，存储方向并使用 BFS() 来降低时间复杂度：

struct Node{
    short row, col;
    char dir;
    Node(int _row = 0, int _col = 0, int _dir = 0){
        row = _row; col = _col; dir = _dir;
    }
};

void BFS(){
    memset(turns, 0x3f, sizeof turns);

    deque<pair<int, Node> > dq;
    for(int i = 0; i < 4; i++){
        Node s(xHome + dx[i], yHome + dy[i], i);
        if(!matrix[s.row][s.col])continue;
        turns[s.row][s.col][s.dir] = 0;
        dq.push_back({0, s});
    }

    while(!dq.empty()){
        int d = dq.front().fi;
        Node u = dq.front().se;
        dq.pop_front();

        if(d != turns[u.row][u.col][u.dir])continue;

        for(int i = 0; i < 4; i++){
            Node v(u.row + dx[i], u.col + dy[i], i);
            if(!matrix[v.row][v.col])continue;

            if(minimize(turns[v.row][v.col][v.dir], turns[u.row][u.col][u.dir] + (i != u.dir))){
                if(i == u.dir)dq.push_front({turns[v.row][v.col][v.dir], v});
                else dq.push_back({turns[v.row][v.col][v.dir], v});
                trace[v.row][v.col][v.dir] = u;
            }
        }
    }
}

在迷宫中找到两点之间的最小转弯路径

Find a path between 2 points in a maze with minimum turns

c++

algorithm

dijkstra

maze