// C++ program to find minimum Cost Path with  // Left Right Bottom and Up moves allowed #include    using namespace std; // Function to check if cell is valid. bool isValidCell(int i int j int n) {  return i>=0 && i<n && j>=0 && j<n; } int minimumCostPath(vector<vector<int>> &grid) {  int n = grid.size();    // Min heap to implement dijkstra  priority_queue<vector<int>   vector<vector<int>> greater<vector<int>>> pq;    // 2d grid to store minimum cost  // to reach every cell.  vector<vector<int>> cost(n vector<int>(n INT_MAX));  cost[0][0] = grid[0][0];    // Direction vector to move in 4 directions  vector<vector<int>> dir = {{-10} {10} {0-1} {01}};    pq.push({grid[0][0] 0 0});    while (!pq.empty()) {  vector<int> top = pq.top();  pq.pop();    int c = top[0] i = top[1] j = top[2];    // Check for all 4 neighbouring cells.  for (auto d: dir) {  int x = i + d[0];  int y = j + d[1];    // If cell is valid and cost to reach this cell   // from current cell is less  if (isValidCell(x y n) &&   cost[i][j]+grid[x][y]<cost[x][y]) {    // Update cost to reach this cell.  cost[x][y] = cost[i][j]+grid[x][y];    // Push the cell into heap.  pq.push({cost[x][y] x y});  }  }  }    // Return minimum cost to   // reach bottom right cell.  return cost[n-1][n-1]; } int main() {  vector<vector<int>> grid =   {{9499}{6764}{8337}{74910}};    cout << minimumCostPath(grid) << endl;    return 0; } 

// Java program to find minimum Cost Path with  // Left Right Bottom and Up moves allowed import java.util.PriorityQueue; import java.util.Arrays; class GfG {  // Function to check if cell is valid.  static boolean isValidCell(int i int j int n) {  return i >= 0 && i < n && j >= 0 && j < n;  }  static int minimumCostPath(int[][] grid) {  int n = grid.length;    // Min heap to implement Dijkstra  PriorityQueue<int[]> pq =   new PriorityQueue<>((a b) -> Integer.compare(a[0] b[0]));    // 2D grid to store minimum cost  // to reach every cell.  int[][] cost = new int[n][n];  for (int[] row : cost) {  Arrays.fill(row Integer.MAX_VALUE);  }  cost[0][0] = grid[0][0];    // Direction vector to move in 4 directions  int[][] dir = {{-1 0} {1 0} {0 -1} {0 1}};    pq.offer(new int[]{grid[0][0] 0 0});    while (!pq.isEmpty()) {  int[] top = pq.poll();    int c = top[0] i = top[1] j = top[2];    // Check for all 4 neighbouring cells.  for (int[] d : dir) {  int x = i + d[0];  int y = j + d[1];    // If cell is valid and cost to reach this cell   // from current cell is less  if (isValidCell(x y n) && cost[i][j] + grid[x][y] < cost[x][y]) {    // Update cost to reach this cell.  cost[x][y] = cost[i][j] + grid[x][y];    // Push the cell into heap.  pq.offer(new int[]{cost[x][y] x y});  }  }  }    // Return minimum cost to   // reach bottom right cell.  return cost[n - 1][n - 1];  }  public static void main(String[] args) {  int[][] grid = {  {9 4 9 9}  {6 7 6 4}  {8 3 3 7}  {7 4 9 10}  };    System.out.println(minimumCostPath(grid));  } } 

# Python program to find minimum Cost Path with  # Left Right Bottom and Up moves allowed import heapq # Function to check if cell is valid. def isValidCell(i j n): return i >= 0 and i < n and j >= 0 and j < n def minimumCostPath(grid): n = len(grid) # Min heap to implement Dijkstra pq = [] # 2D grid to store minimum cost # to reach every cell. cost = [[float('inf')] * n for _ in range(n)] cost[0][0] = grid[0][0] # Direction vector to move in 4 directions dir = [[-1 0] [1 0] [0 -1] [0 1]] heapq.heappush(pq [grid[0][0] 0 0]) while pq: c i j = heapq.heappop(pq) # Check for all 4 neighbouring cells. for d in dir: x y = i + d[0] j + d[1] # If cell is valid and cost to reach this cell  # from current cell is less if isValidCell(x y n) and cost[i][j] + grid[x][y] < cost[x][y]: # Update cost to reach this cell. cost[x][y] = cost[i][j] + grid[x][y] # Push the cell into heap. heapq.heappush(pq [cost[x][y] x y]) # Return minimum cost to  # reach bottom right cell. return cost[n - 1][n - 1] if __name__ == '__main__': grid = [ [9 4 9 9] [6 7 6 4] [8 3 3 7] [7 4 9 10] ] print(minimumCostPath(grid)) 

// C# program to find minimum Cost Path with  // Left Right Bottom and Up moves allowed using System; using System.Collections.Generic; class GfG {  // Function to check if cell is valid.  static bool isValidCell(int i int j int n) {  return i >= 0 && i < n && j >= 0 && j < n;  }  static int minimumCostPath(int[][] grid) {  int n = grid.Length;    // Min heap to implement Dijkstra  var pq = new SortedSet<(int cost int x int y)>();    // 2D grid to store minimum cost  // to reach every cell.  int[][] cost = new int[n][];  for (int i = 0; i < n; i++) {  cost[i] = new int[n];  Array.Fill(cost[i] int.MaxValue);  }  cost[0][0] = grid[0][0];    // Direction vector to move in 4 directions  int[][] dir = { new int[] {-1 0} new int[] {1 0}   new int[] {0 -1} new int[] {0 1} };    pq.Add((grid[0][0] 0 0));    while (pq.Count > 0) {  var top = pq.Min;  pq.Remove(top);    int i = top.x j = top.y;    // Check for all 4 neighbouring cells.  foreach (var d in dir) {  int x = i + d[0];  int y = j + d[1];    // If cell is valid and cost to reach this cell   // from current cell is less  if (isValidCell(x y n) &&   cost[i][j] + grid[x][y] < cost[x][y]) {    // Update cost to reach this cell.  cost[x][y] = cost[i][j] + grid[x][y];    // Push the cell into heap.  pq.Add((cost[x][y] x y));  }  }  }    // Return minimum cost to   // reach bottom right cell.  return cost[n - 1][n - 1];  }  static void Main(string[] args) {  int[][] grid = new int[][] {  new int[] {9 4 9 9}  new int[] {6 7 6 4}  new int[] {8 3 3 7}  new int[] {7 4 9 10}  };    Console.WriteLine(minimumCostPath(grid));  } } 

// JavaScript program to find minimum Cost Path with // Left Right Bottom and Up moves allowed function comparator(a b) {  if (a[0] > b[0]) return -1;  if (a[0] < b[0]) return 1;  return 0; } class PriorityQueue {  constructor(compare) {  this.heap = [];  this.compare = compare;  }  enqueue(value) {  this.heap.push(value);  this.bubbleUp();  }  bubbleUp() {  let index = this.heap.length - 1;  while (index > 0) {  let element = this.heap[index]  parentIndex = Math.floor((index - 1) / 2)  parent = this.heap[parentIndex];  if (this.compare(element parent) < 0) break;  this.heap[index] = parent;  this.heap[parentIndex] = element;  index = parentIndex;  }  }  dequeue() {  let max = this.heap[0];  let end = this.heap.pop();  if (this.heap.length > 0) {  this.heap[0] = end;  this.sinkDown(0);  }  return max;  }  sinkDown(index) {  let left = 2 * index + 1  right = 2 * index + 2  largest = index;  if (  left < this.heap.length &&  this.compare(this.heap[left] this.heap[largest]) > 0  ) {  largest = left;  }  if (  right < this.heap.length &&  this.compare(this.heap[right] this.heap[largest]) > 0  ) {  largest = right;  }  if (largest !== index) {  [this.heap[largest] this.heap[index]] = [  this.heap[index]  this.heap[largest]  ];  this.sinkDown(largest);  }  }  isEmpty() {  return this.heap.length === 0;  } } // Function to check if cell is valid. function isValidCell(i j n) {  return i >= 0 && i < n && j >= 0 && j < n; } function minimumCostPath(grid) {  let n = grid.length;  // Min heap to implement Dijkstra  const pq = new PriorityQueue(comparator)  // 2D grid to store minimum cost  // to reach every cell.  let cost = Array.from({ length: n } () => Array(n).fill(Infinity));  cost[0][0] = grid[0][0];  // Direction vector to move in 4 directions  let dir = [[-1 0] [1 0] [0 -1] [0 1]];  pq.enqueue([grid[0][0] 0 0]);  while (!pq.isEmpty()) {  let [c i j] = pq.dequeue();  // Check for all 4 neighbouring cells.  for (let d of dir) {  let x = i + d[0];  let y = j + d[1];  // If cell is valid and cost to reach this cell  // from current cell is less  if (isValidCell(x y n) && cost[i][j] + grid[x][y] < cost[x][y]) {  // Update cost to reach this cell.  cost[x][y] = cost[i][j] + grid[x][y];  // Push the cell into heap.  pq.enqueue([cost[x][y] x y]);  }  }  }  // Return minimum cost to  // reach bottom right cell.  return cost[n - 1][n - 1]; } let grid = [  [9 4 9 9]  [6 7 6 4]  [8 3 3 7]  [7 4 9 10]  ]; console.log(minimumCostPath(grid));