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

//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; } }