A* Search — Heuristic Shortest Path for Grid Problems

import heapq

def astar(grid, start, end):
    rows, cols = len(grid), len(grid[0])
    sr, sc = start
    er, ec = end

    def h(r, c):
        return abs(r-er) + abs(c-ec)

    heap = [(h(sr,sc), 0, sr, sc)]
    dist = {(sr,sc): 0}

    while heap:
        f, g, r, c = heapq.heappop(heap)
        if (r,c) == (er,ec): return g
        if g > dist.get((r,c), float('inf')): continue
        for dr,dc in [(-1,0),(1,0),(0,-1),(0,1)]:
            nr,nc = r+dr,c+dc
            if 0<=nr<rows and 0<=nc<cols and grid[nr][nc]!=1:
                ng = g+1
                if ng < dist.get((nr,nc), float('inf')):
                    dist[(nr,nc)] = ng
                    heapq.heappush(heap, (ng+h(nr,nc), ng, nr, nc))
    return -1

function astar(grid, [sr,sc], [er,ec]) {
    const h=(r,c)=>Math.abs(r-er)+Math.abs(c-ec);
    const dist=new Map([[sr+','+sc,0]]);
    const heap=[[h(sr,sc),0,sr,sc]];
    const pop=()=>{let mi=0;for(let i=1;i<heap.length;i++)if(heap[i][0]<heap[mi][0])mi=i;return heap.splice(mi,1)[0];};
    while(heap.length){
        const[f,g,r,c]=pop();
        if(r===er&&c===ec)return g;
        if(g>dist.get(r+','+c))continue;
        for(const[dr,dc]of[[-1,0],[1,0],[0,-1],[0,1]]){
            const[nr,nc]=[r+dr,c+dc];
            if(nr>=0&&nr<grid.length&&nc>=0&&nc<grid[0].length&&grid[nr][nc]!==1){
                const ng=g+1,k=nr+','+nc;
                if(ng<(dist.get(k)??Infinity)){dist.set(k,ng);heap.push([ng+h(nr,nc),ng,nr,nc]);}
            }
        }
    }
    return -1;
}

import java.util.*;
public int astar(int[][] grid, int[] s, int[] e) {
    int R=grid.length,C=grid[0].length,er=e[0],ec=e[1];
    int[][] dist=new int[R][C]; for(int[]r:dist)Arrays.fill(r,Integer.MAX_VALUE);
    dist[s[0]][s[1]]=0;
    PriorityQueue<int[]> pq=new PriorityQueue<>(Comparator.comparingInt(a->a[0]));
    pq.offer(new int[]{Math.abs(s[0]-er)+Math.abs(s[1]-ec),0,s[0],s[1]});
    int[][]dirs={{-1,0},{1,0},{0,-1},{0,1}};
    while(!pq.isEmpty()){
        int[]top=pq.poll(); int g=top[1],r=top[2],c=top[3];
        if(r==er&&c==ec)return g;
        if(g>dist[r][c])continue;
        for(int[]d:dirs){int nr=r+d[0],nc=c+d[1];
            if(nr>=0&&nr<R&&nc>=0&&nc<C&&grid[nr][nc]!=1&&g+1<dist[nr][nc]){
                dist[nr][nc]=g+1;pq.offer(new int[]{g+1+Math.abs(nr-er)+Math.abs(nc-ec),g+1,nr,nc});}}
    }
    return -1;
}

#include <queue>
#include <vector>
#include <tuple>
using namespace std;
int astar(vector<vector<int>>&grid,pair<int,int>s,pair<int,int>e){
    int R=grid.size(),C=grid[0].size(),er=e.first,ec=e.second;
    vector<vector<int>> dist(R,vector<int>(C,INT_MAX));
    auto h=[&](int r,int c){return abs(r-er)+abs(c-ec);};
    priority_queue<tuple<int,int,int,int>,vector<tuple<int,int,int,int>>,greater<>> pq;
    dist[s.first][s.second]=0; pq.push({h(s.first,s.second),0,s.first,s.second});
    int dirs[]={-1,0,1,0,-1};
    while(!pq.empty()){
        auto[f,g,r,c]=pq.top();pq.pop();
        if(r==er&&c==ec)return g; if(g>dist[r][c])continue;
        for(int d=0;d<4;d++){int nr=r+dirs[d],nc=c+dirs[d+1];
            if(nr>=0&&nr<R&&nc>=0&&nc<C&&grid[nr][nc]!=1&&g+1<dist[nr][nc]){
                dist[nr][nc]=g+1;pq.push({g+1+h(nr,nc),g+1,nr,nc});}}
    }
    return -1;
}

/* C: same min-heap approach, Manhattan heuristic with int arithmetic */