Optimizing Grid-Based Pathfinding With Dijkstra's Algorithm
BFS algorithm used to find min cost path in grid with obstacles. Time complexity O(n*mlog(n*m)), space complexity O(m*n).
Problem
Same as Minimum Obstacle removal to reach corner
Time Complexity: O(n*mlog(n*m)
Space Complexity: O(m*n)
//BFS : dijkstras
class Solution {
public int minCost(int[][] grid) {
// consider each cell as a node and choose nodes that are reachable in shorted distance possible from the current node
PriorityQueue<Cell> queue = new PriorityQueue<>((a,b)-> Integer.compare(a.c,b.c));
int cost =0;// min cost to reach to the goal node
queue.add(new Cell(0,0,0,grid[0][0]));//start with the first cell (i,j,cost,direction)
int visited[][] = new int[grid.l...