I am solving the question of shortest path in binary matrix. Ques_Link
I used A* algorithm which is supposed to be better than Dijkstra in such cases (“Manhattan block example”). But it is apparently beating only 5% other users and the ones which are at the top have used Dijkstra in their solution. Is introducing this heuristic a bad idea?
class Solution {
public:
int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
int n = grid.size();
if(grid[0][0] || grid[n-1][n-1])
return -1;
priority_queue<pair<pair<double,int>,pair<int,int>>,vector<pair<pair<double,int>,pair<int,int>>>,
greater<pair<pair<double,int>,pair<int,int>>>> pq;
vector<vector<int>> dist(n,vector<int>(n,1e9));
dist[0][0]=0;
int heur = (sqrt(2)*(n-1));
pq.push({{heur,0},{0,0}});
int delrow[] = {-1,-1,-1, 0, 1, 1, 1, 0};
int delcol[] = {-1, 0, 1, 1, 1, 0,-1,-1};
while(!pq.empty())
{
auto it = pq.top();
pq.pop();
// int astar_dist = it.first.first;
int dijk_dist = it.first.second;
int row = it.second.first;
int col = it.second.second;
for(int i=0;i<8;i++)
{
int nrow = row + delrow[i];
int ncol = col + delcol[i];
if(nrow>=0 && nrow<n && ncol>=0 && ncol<n && grid[nrow][ncol]==0 && dist[nrow][ncol]>dijk_dist+1)
{
dist[nrow][ncol]=dijk_dist+1;
int temp_dist = (sqrt((n-1-nrow)*(n-1-row) + (n-1-col)*(n-1-col)));
pq.push({{temp_dist,dijk_dist+1},{nrow,ncol}});
}
}
}
if(dist[n-1][n-1]==1e9)
return -1;
return dist[n-1][n-1]+1;
}
};
This is what I tried. Is it my implementation of A* which is causing an issue or the testcases of LeetCode are designed for implementing Dijkstra algorithm?
Shubham Shah is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.