C++ Solution using Dijkshtra Algorithm

 
class Point{
    public:
    int x;
    int y;
    int cost;
};
struct comp{
    bool operator()(Point const& p1, Point const& p2){
        return p1.cost>p2.cost;//mid priority_queue
    }
};
// R,D,L,U
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};

int Solution::solve(int r, int c, vector<string> &mat) {
    string s="RDLU"; // all for possible directions
    // to store distance
    vector<vector<int>>dist(r,vector<int>(c,INT_MAX-1));
    // to get min cost path
    priority_queue<Point,vector<Point>,comp>pq;
    // let's push initial co-ordinates
    pq.push({0,0,0});
    dist[0][0]=0;
    while(!pq.empty()){
        Point cp=pq.top();
        pq.pop();
        if(cp.x==r-1 and cp.y==c-1) return dist[cp.x][cp.y];
        for(int i=0;i<4;i++){
            int nx=cp.x+dx[i];
            int ny=cp.y+dy[i];
            int cost=dist[cp.x][cp.y];
            if(s[i]!=mat[cp.x][cp.y]) cost++;
            
            //check boundary condition and cost
            if(nx>=0 and ny>=0 and nx<r and ny<c and cost<dist[nx][ny]){
                pq.push({nx,ny,cost});
                dist[nx][ny]=cost;
            }
        }
    }
    return dist[r-1][c-1];
}

Click here to start solving coding interview questions