MinCostPath

#define ar array<int,2>
map<pair<int,int>,char>mp{{{1,0},'R'},{{0,1},'U'},{{-1,0},'L'},{{0,-1},'D'}};
vector<array<int,2> >dirs{{1,0},{0,1},{-1,0},{0,-1}};
int bfs(vector<vector<char>>&g){
    int n=g.size(),m=g[0].size();
    auto isvalid = [&] (int x, int y)-> bool {
        return x>=0 and x<n and y>=0 and y<m;
    };
    deque<ar>q;
    vector<vector<int>>dis(n,vector<int>(m,n+m));
    vector<vector<bool>>vis(n,vector<bool>(m,false));
    q.push_front({0,0});
    dis[0][0]=0;
    vis[0][0]=true;
    while(!q.empty()){
        auto [i,j] = q.front();
        q.pop_front();
        for(auto dir:dirs){
            int ni = i+dir[0],nj=j+dir[1];
            if(isvalid(ni,nj) and !vis[ni][nj] and mp[make_pair(dir[0],dir[1])] == g[i][j] and dis[ni][nj]>dis[i][j]) {
                dis[ni][nj] = dis[i][j];
                q.push_front({ni,nj});
            }

            if(isvalid(ni,nj) and !vis[ni][nj] and mp[make_pair(dir[0],dir[1])] != g[i][j] and dis[ni][nj]>dis[i][j] +1 ) {
                dis[ni][nj] = dis[i][j]+1;
                q.push_back({ni,nj});
            }
        }
    }
    return dis[n-1][m-1];
}
int Solution::solve(int A, int B, vector<string> &C) {
    vector<vector<char>>g(A,vector<char>(B));
    for(int i=0;i<A;i++){
        for(int j=0;j<B;j++) {
            g[i][j] = C[i][j];
        }
    }
   return bfs(g);
}