class Solution { public int minCost(int[][] grid) { /* already submitted a solution using BFS and DP this one is simple solution using Djikstra and DP //we will not use pair class instead use array and lambda function */ int m = grid.length, n = grid[0].length; PriorityQueue<int[]> q = new PriorityQueue<>((a,b) -> a[2] - b[2]); q.add(new int[]{0 , 0 ,0}); /* we will make a dp array which will store minimum cost for every cell , this is to avoid using visited.. as a new path can overlap an old path if it has a lesser path cost we will make this a dp array and not visited cause then a new path will not be able to overlap a previous path as that cell will already be true */ int[][] costs = new int[m][n]; //dp array for(int temp[] : costs) //filling dp array Arrays.fill(temp , Integer.MAX_VALUE); //djikstra algo while(q.size() > 0){ int[] rem = q.remove(); int row = rem[0] , col = rem[1] , cost = rem[2]; if(row == m-1 && col == n-1) return cost; //seeing neighours for(int i = 0 ; i < 4 ; i++){ int rowdash = row + dir[i][0]; int coldash = col + dir[i][1]; //if valid cell if(rowdash >= 0 && coldash >= 0 && rowdash < m && coldash < n ){ /* if new cost is < previous cost we update even if we have to revsit the node -- this is alternate to visited array */ int new_cost = cost + (i+1 == grid[row][col] ? 0 : 1); if(new_cost < costs[rowdash][coldash]){ costs[rowdash][coldash] = new_cost; q.add(new int[]{rowdash , coldash , new_cost}); } } } } return 69; } public int[][] dir = {{0,1}, {0,-1} , {1,0} , {-1,0}}; //right , left , down , up }