1368-1

class Solution {

struct compare{
    bool operator()(pair<pair<int, int>, int> a, pair<pair<int, int>, int> b){
        return a.second > b.second;
    }
};

public:
    int minCost(vector<vector<int>>& grid) {
        int dirs[5][2] = {{0,0}, {0,1}, {0,-1}, {1,0}, {-1,0}};
        const int INF = INT_MAX;
        int rows = grid.size(), cols = grid[0].size();
        int cost[rows][cols];

        for(int i=0; i<rows; i++)
            for(int j=0; j<cols; j++)
                cost[i][j] = INF;

        priority_queue<pair<pair<int, int>, int>, vector<pair<pair<int, int>, int>>, compare> q;
        q.push({{0, 0}, 0});
        cost[0][0] = 0;

        while(!q.empty()){
            auto p = q.top();
            q.pop();
            int curX = p.first.first, curY = p.first.second;
            int curDist = p.second;
            for(int dir=1; dir<=4; dir++){
                int nextX = curX+dirs[dir][0], nextY = curY+dirs[dir][1];
                if(nextX >= 0 && nextX < rows && nextY >=0 && nextY < cols){
                    int weight = (dir == grid[curX][curY]) ? 0 : 1;
                    if(curDist+weight < cost[nextX][nextY]){
                        cost[nextX][nextY] = curDist+weight;
                        q.push({{nextX, nextY}, cost[nextX][nextY]});
                    }
                }
            }
        }
        return cost[rows-1][cols-1];
    }
};