c++ dijkstra's algorithm (30ms)


  • 0
    T
    struct Position {
        int x_, y_, d_;
        Position(int x, int y, int d):x_(x), y_(y), d_(d) {}
    };
    
    class Solution {
    public:
        int shortestDistance(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {
            if (maze.empty()) {
                return -1;
            }
            auto compare = [](Position &p1, Position &p2) { return p1.d_ > p2.d_; };
            priority_queue<Position, vector<Position>, decltype(compare)> pq(compare);
            pq.emplace(Position(start[0], start[1], 0));
            
            int dir[5] = {0,1,0,-1,0}, h = maze.size(), w = maze[0].size();
            vector<vector<int>> dist(h, vector<int>(w, INT_MAX));
            
            while (!pq.empty()) {
                auto p = pq.top(); pq.pop();
                int x = p.x_, y = p.y_, d = p.d_;
                if (x == destination[0] && y == destination[1]) {
                    return d;
                }
                dist[x][y] = d;
                for (int i = 0; i < 4; ++i) {
                    int nx = x, ny = y, nd = d;
                    while (nx+dir[i] < h && nx+dir[i] >= 0 && 
                           ny+dir[i+1] < w && ny+dir[i+1] >= 0 && 
                        !maze[nx+dir[i]][ny+dir[i+1]]) {
                        nx += dir[i], ny += dir[i+1], ++nd;
                    }
                    if (dist[nx][ny] > nd) {
                        dist[nx][ny] = nd;
                        pq.emplace(Position(nx, ny, nd));
                    }
                }
            }
            return -1;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.