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

Question

The problem:

Given a 2D matrix consist of 0 and 1, you can only go in location with 1. Start at point (x, y), we can move to 4 adjacent points: up, down, left, right; which are: (x+1, y), (x-1, y), (x, y+1), (x, y-1).

Find a path from point (x, y) to point (s, t) so that it has the least number of turns.

My question:

I tried to solve this problem using dijsktra, it got most of the cases right, but in some cases, it didn't give the most optimal answer.

Here's my code:

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: The main solving is in void dijkstra, the others are just to give some more information in case you guys need it.

Answer 1

I have found a way to solve this problem, storing directions and using BFS() to reduce the time complexity:

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;
            }
        }
    }
}