1368. Minimum Cost to Make at Least One Valid Path in a Grid

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.length][grid[0].length];

        while(!queue.isEmpty()){
            Cell cell = queue.remove();
            //check for all the neighbouring cells of the current cell and add them
            // in the queue with additional cost if incurred
            int I = cell.i;
            int J = cell.j;
            if(visited[I][J]==1) continue;
            visited[I][J] = 1;
            //if we have reached the goal node break out 
            if(I == grid.length-1 && J == grid[0].length-1) {
                cost = cell.c;// the goal node cost
                break;
            }
            int costSoFar=cell.c;// cost till the current node
            int dirs[][] = {{0,1},{0,-1},{1,0},{-1,0}};
            // from current node(I,J) we can move in 4 directions right,left,down,and up
            for(int d = 0;d<dirs.length;d++){ //0(1:right),1(2:left),2(3:down),3(4:up) i.e index + 1 offset will give the direction of movement 
                int i = I+dirs[d][0];
                int j = J+dirs[d][1];
                //(i,j) is the new node make sure it is not out of grid and not visited previously
                if(i>=0 && j>=0 && i<grid.length && j<grid[0].length && visited[i][j]==0){
                    int c = costSoFar;//cost till the currentNode (I,J)
                    if(grid[I][J] != (d+1)) c+= 1; // if we moving in the same direction, no addition cost will be applied else cost of 1 will inccur
                    queue.add(new Cell(i,j,c,grid[i][j]));
                }
            }
        }
        return cost;
    }
}
class Cell{
    public int i;
    public int j;
    public int c;
    public int d;
    public Cell(int i, int j, int c, int d){
        this.i = i;
        this.j = j;
        this.c = c;
        this.d = d;
    }
}