# c++ dijkstra's algorithm (30ms)

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

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