1368-2

class Solution {
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;

        deque<pair<int, int>> q;
        q.push_back({0, 0});
        cost[0][0] = 0;

        while(!q.empty()){
            auto p = q.front();
            q.pop_front();
            int curX = p.first, curY = p.second;
            int curDist = cost[curX][curY];
            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;
                        if(weight)
                            q.push_back({nextX, nextY});
                        else
                            q.push_front({nextX, nextY});
                    }
                }
            }
        }
        return cost[rows-1][cols-1];
    }
};