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
    
}