import heapq
 
def a_star_grid(grid, start, end):
    """
    A* Search on a 2D grid.
    Time: O(E log V) | Space: O(V)
    Returns the path as list of coordinates, or empty if not found.
    """
    rows, cols = len(grid), len(grid[0])
    
    def heuristic(r, c):
        # Manhattan distance
        return abs(r - end[0]) + abs(c - end[1])
 
    # Heap storing: (f_score, g_score, (row, col))
    open_set = []
    heapq.heappush(open_set, (heuristic(start[0], start[1]), 0, start))
    
    parent = {}
    g_score = {start: 0}
    closed_set = set()
 
    while open_set:
        f, g, curr = heapq.heappop(open_set)
        
        if curr == end:
            # Reconstruct path
            path = []
            while curr in parent:
                path.append(curr)
                curr = parent[curr]
            path.append(start)
            return path[::-1]
        
        if curr in closed_set:
            continue
        closed_set.add(curr)
 
        r, c = curr
        for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            nr, nc = r + dr, c + dc
            neighbor = (nr, nc)
            
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 0:
                if neighbor in closed_set:
                    continue
                
                temp_g = g + 1
                if temp_g < g_score.get(neighbor, float('inf')):
                    g_score[neighbor] = temp_g
                    f_score = temp_g + heuristic(nr, nc)
                    parent[neighbor] = curr
                    heapq.heappush(open_set, (f_score, temp_g, neighbor))
                    
    return [] # Path not found
 
# Example Setup
grid = [
    [0, 1, 0, 0],
    [0, 1, 0, 0],
    [0, 0, 0, 1],
    [0, 1, 0, 0]
]
print("Path found:", a_star_grid(grid, (0, 0), (3, 2)))
# Output: [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2), (3, 2)]

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <unordered_map>
#include <set>
#include <algorithm>
 
struct Node {
    int r, c;
    int f, g;
    bool operator>(const Node& other) const {
        return f > other.f;
    }
};
 
// Hash function for pair coordinates
struct PairHash {
    std::size_t operator()(const std::pair<int, int>& p) const {
        return (p.first * 31) ^ p.second;
    }
};
 
std::vector<std::pair<int, int>> aStarGrid(const std::vector<std::vector<int>>& grid, 
                                          std::pair<int, int> start, std::pair<int, int> end) {
    int rows = grid.size();
    int cols = grid[0].size();
 
    auto heuristic = [&](int r, int c) {
        return std::abs(r - end.first) + std::abs(c - end.second);
    };
 
    std::priority_queue<Node, std::vector<Node>, std::greater<Node>> openSet;
    openSet.push({start.first, start.second, heuristic(start.first, start.second), 0});
 
    std::unordered_map<std::pair<int, int>, std::pair<int, int>, PairHash> parent;
    std::unordered_map<std::pair<int, int>, int, PairHash> gScore;
    gScore[start] = 0;
 
    std::set<std::pair<int, int>> closedSet;
    std::vector<std::pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
 
    while (!openSet.empty()) {
        Node curr = openSet.top();
        openSet.pop();
        std::pair<int, int> currPair = {curr.r, curr.c};
 
        if (currPair == end) {
            std::vector<std::pair<int, int>> path;
            while (parent.find(currPair) != parent.end()) {
                path.push_back(currPair);
                currPair = parent[currPair];
            }
            path.push_back(start);
            std::reverse(path.begin(), path.end());
            return path;
        }
 
        if (closedSet.find(currPair) != closedSet.end()) continue;
        closedSet.insert(currPair);
 
        for (auto& dir : directions) {
            int nr = curr.r + dir.first;
            int nc = curr.c + dir.second;
            std::pair<int, int> neighbor = {nr, nc};
 
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 0) {
                if (closedSet.find(neighbor) != closedSet.end()) continue;
 
                int tempG = curr.g + 1;
                if (gScore.find(neighbor) == gScore.end() || tempG < gScore[neighbor]) {
                    gScore[neighbor] = tempG;
                    int fScore = tempG + heuristic(nr, nc);
                    parent[neighbor] = currPair;
                    openSet.push({nr, nc, fScore, tempG});
                }
            }
        }
    }
    return {};
}
 
int main() {
    std::vector<std::vector<int>> grid = {
        {0, 1, 0, 0},
        {0, 1, 0, 0},
        {0, 0, 0, 1},
        {0, 1, 0, 0}
    };
    std::vector<std::pair<int, int>> path = aStarGrid(grid, {0, 0}, {3, 2});
    std::cout << "Path: ";
    for (auto& cell : path) {
        std::cout << "(" << cell.first << "," << cell.second << ") ";
    }
    std::cout << "\n";
    return 0;
}

// Complete A* Search with Custom Binary Min-Heap
class MinHeap {
    constructor() {
        this.data = [];
    }
    push(item) {
        this.data.push(item);
        this.up(this.data.length - 1);
    }
    pop() {
        if (this.data.length === 0) return null;
        const top = this.data[0];
        const bottom = this.data.pop();
        if (this.data.length > 0) {
            this.data[0] = bottom;
            this.down(0);
        }
        return top;
    }
    size() {
        return this.data.length;
    }
    up(i) {
        while (i > 0) {
            const p = Math.floor((i - 1) / 2);
            if (this.data[p].f <= this.data[i].f) break;
            const tmp = this.data[p];
            this.data[p] = this.data[i];
            this.data[i] = tmp;
            i = p;
        }
    }
    down(i) {
        const len = this.data.length;
        while (i * 2 + 1 < len) {
            let child = i * 2 + 1;
            if (child + 1 < len && this.data[child + 1].f < this.data[child].f) {
                child++;
            }
            if (this.data[i].f <= this.data[child].f) break;
            const tmp = this.data[child];
            this.data[child] = this.data[i];
            this.data[i] = tmp;
            i = child;
        }
    }
}
 
function aStarGrid(grid, start, end) {
    const rows = grid.length;
    const cols = grid[0].length;
 
    function heuristic(r, c) {
        return Math.abs(r - end[0]) + Math.abs(c - end[1]);
    }
 
    const heap = new MinHeap();
    heap.push({ r: start[0], c: start[1], f: heuristic(start[0], start[1]), g: 0 });
 
    const parent = {};
    const gScore = {};
    gScore[`${start[0]},${start[1]}`] = 0;
    const closedSet = new Set();
 
    while (heap.size() > 0) {
        const curr = heap.pop();
        const key = `${curr.r},${curr.c}`;
 
        if (curr.r === end[0] && curr.c === end[1]) {
            const path = [];
            let currKey = key;
            while (parent[currKey]) {
                const [r, c] = currKey.split(',').map(Number);
                path.push([r, c]);
                currKey = parent[currKey];
            }
            path.push(start);
            return path.reverse();
        }
 
        if (closedSet.has(key)) continue;
        closedSet.add(key);
 
        const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
        for (const [dr, dc] of directions) {
            const nr = curr.r + dr;
            const nc = curr.c + dc;
            const nKey = `${nr},${nc}`;
 
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] === 0) {
                if (closedSet.has(nKey)) continue;
 
                const tempG = curr.g + 1;
                if (gScore[nKey] === undefined || tempG < gScore[nKey]) {
                    gScore[nKey] = tempG;
                    const fScore = tempG + heuristic(nr, nc);
                    parent[nKey] = key;
                    heap.push({ r: nr, c: nc, f: fScore, g: tempG });
                }
            }
        }
    }
    return [];
}
 
const grid = [
    [0, 1, 0, 0],
    [0, 1, 0, 0],
    [0, 0, 0, 1],
    [0, 1, 0, 0]
];
console.log("Path:", aStarGrid(grid, [0, 0], [3, 2]));
// Output: [ [ 0, 0 ], [ 1, 0 ], [ 2, 0 ], [ 2, 1 ], [ 2, 2 ], [ 3, 2 ] ]

import java.util.*;
 
public class AStar {
    static class Node implements Comparable<Node> {
        int r, c, f, g;
        Node(int r, int c, int f, int g) {
            this.r = r;
            this.c = c;
            this.f = f;
            this.g = g;
        }
        public int compareTo(Node other) {
            return Integer.compare(this.f, other.f);
        }
    }
 
    public static List<int[]> aStarGrid(int[][] grid, int[] start, int[] end) {
        int rows = grid.length;
        int cols = grid[0].length;
 
        PriorityQueue<Node> openSet = new PriorityQueue<>();
        openSet.add(new Node(start[0], start[1], Math.abs(start[0] - end[0]) + Math.abs(start[1] - end[1]), 0));
 
        Map<String, String> parent = new HashMap<>();
        Map<String, Integer> gScore = new HashMap<>();
        gScore.put(start[0] + "," + start[1], 0);
        Set<String> closedSet = new HashSet<>();
 
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
 
        while (!openSet.isEmpty()) {
            Node curr = openSet.poll();
            String currKey = curr.r + "," + curr.c;
 
            if (curr.r == end[0] && curr.c == end[1]) {
                List<int[]> path = new ArrayList<>();
                String tmp = currKey;
                while (parent.containsKey(tmp)) {
                    String[] split = tmp.split(",");
                    path.add(new int[]{Integer.parseInt(split[0]), Integer.parseInt(split[1])});
                    tmp = parent.get(tmp);
                }
                path.add(start);
                Collections.reverse(path);
                return path;
            }
 
            if (closedSet.contains(currKey)) continue;
            closedSet.add(currKey);
 
            for (int[] d : directions) {
                int nr = curr.r + d[0];
                int nc = curr.c + d[1];
                String nKey = nr + "," + nc;
 
                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 0) {
                    if (closedSet.contains(nKey)) continue;
 
                    int tempG = curr.g + 1;
                    if (!gScore.containsKey(nKey) || tempG < gScore.get(nKey)) {
                        gScore.put(nKey, tempG);
                        int fScore = tempG + Math.abs(nr - end[0]) + Math.abs(nc - end[1]);
                        parent.put(nKey, currKey);
                        openSet.add(new Node(nr, nc, fScore, tempG));
                    }
                }
            }
        }
        return new ArrayList<>();
    }
 
    public static void main(String[] args) {
        int[][] grid = {
            {0, 1, 0, 0},
            {0, 1, 0, 0},
            {0, 0, 0, 1},
            {0, 1, 0, 0}
        };
        List<int[]> path = aStarGrid(grid, new int[]{0, 0}, new int[]{3, 2});
        System.out.print("Path: ");
        for (int[] cell : path) {
            System.out.print("(" + cell[0] + "," + cell[1] + ") ");
        }
        System.out.println();
    }
}

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>
 
#define ROWS 4
#define COLS 4
 
struct Node {
    int r, c;
    int f, g;
};
 
// Simple C Min-Heap implementation
struct MinHeap {
    struct Node* data;
    int capacity;
    int size;
};
 
struct MinHeap* createMinHeap(int capacity) {
    struct MinHeap* heap = (struct MinHeap*)malloc(sizeof(struct MinHeap));
    heap->capacity = capacity;
    heap->size = 0;
    heap->data = (struct Node*)malloc(capacity * sizeof(struct Node));
    return heap;
}
 
void swap(struct Node* a, struct Node* b) {
    struct Node temp = *a;
    *a = *b;
    *b = temp;
}
 
void push(struct MinHeap* heap, struct Node node) {
    heap->data[heap->size] = node;
    int i = heap->size++;
    while (i > 0) {
        int p = (i - 1) / 2;
        if (heap->data[p].f <= heap->data[i].f) break;
        swap(&heap->data[p], &heap->data[i]);
        i = p;
    }
}
 
struct Node pop(struct MinHeap* heap) {
    struct Node top = heap->data[0];
    heap->data[0] = heap->data[--heap->size];
    int i = 0;
    while (i * 2 + 1 < heap->size) {
        int child = i * 2 + 1;
        if (child + 1 < heap->size && heap->data[child + 1].f < heap->data[child].f) {
            child++;
        }
        if (heap->data[i].f <= heap->data[child].f) break;
        swap(&heap->data[i], &heap->data[child]);
        i = child;
    }
    return top;
}
 
int heuristic(int r, int c, int tr, int tc) {
    return abs(r - tr) + abs(c - tc);
}
 
void aStar(int grid[ROWS][COLS], int sr, int sc, int tr, int tc) {
    struct MinHeap* heap = createMinHeap(100);
    struct Node start = {sr, sc, heuristic(sr, sc, tr, tc), 0};
    push(heap, start);
 
    int gScore[ROWS][COLS];
    int parentR[ROWS][COLS];
    int parentC[ROWS][COLS];
    bool closedSet[ROWS][COLS];
 
    for (int i = 0; i < ROWS; i++) {
        for (int j = 0; j < COLS; j++) {
            gScore[i][j] = 1e9;
            closedSet[i][j] = false;
            parentR[i][j] = -1;
            parentC[i][j] = -1;
        }
    }
    gScore[sr][sc] = 0;
 
    int dRow[] = {-1, 1, 0, 0};
    int dCol[] = 0, dColMap[] = {0, 0, -1, 1}; // 4 directions
 
    bool found = false;
    while (heap->size > 0) {
        struct Node curr = pop(heap);
        if (curr.r == tr && curr.c == tc) {
            found = true;
            break;
        }
 
        if (closedSet[curr.r][curr.c]) continue;
        closedSet[curr.r][curr.c] = true;
 
        for (int i = 0; i < 4; i++) {
            int nr = curr.r + dRow[i];
            int nc = curr.c + dColMap[i];
 
            if (nr >= 0 && nr < ROWS && nc >= 0 && nc < COLS && grid[nr][nc] == 0) {
                if (closedSet[nr][nc]) continue;
 
                int tempG = curr.g + 1;
                if (tempG < gScore[nr][nc]) {
                    gScore[nr][nc] = tempG;
                    int fScore = tempG + heuristic(nr, nc, tr, tc);
                    parentR[nr][nc] = curr.r;
                    parentC[nr][nc] = curr.c;
                    struct Node neighbor = {nr, nc, fScore, tempG};
                    push(heap, neighbor);
                }
            }
        }
    }
 
    if (found) {
        printf("Path found: ");
        int cr = tr, cc = tc;
        int pathR[100], pathC[100], pathLen = 0;
        while (cr != -1 && cc != -1) {
            pathR[pathLen] = cr;
            pathC[pathLen] = cc;
            pathLen++;
            int tempR = parentR[cr][cc];
            int tempC = parentC[cr][cc];
            cr = tempR;
            cc = tempC;
        }
        for (int i = pathLen - 1; i >= 0; i--) {
            printf("(%d,%d) ", pathR[i], pathC[i]);
        }
        printf("\n");
    } else {
        printf("Path not found\n");
    }
    free(heap->data);
    free(heap);
}
 
int main() {
    int grid[ROWS][COLS] = {
        {0, 1, 0, 0},
        {0, 1, 0, 0},
        {0, 0, 0, 1},
        {0, 1, 0, 0}
    };
    aStar(grid, 0, 0, 3, 2);
    return 0;
}