#1

bool is_valid(int x, int y, int m, int n){
if(x < 0 or x >= m or y < 0 or y >= n)
return false;
return true;
}
int dfs(int x, int y, int cost, int m, int n, vector &graph, vector<vector> &node_cost){
node_cost[x][y] = min(node_cost[x][y], cost);
if(x == m-1 and y == n-1)
return node_cost[x][y];
int total_cost = INT_MAX;
int posx[] = {-1, 0, 0, 1};
int posy[] = {0, -1, 1, 0};
char movement[] = {‘U’, ‘L’, ‘R’, ‘D’};
for(int i = 0; i < 4; i++){
int nx = x + posx[i], ny = y + posy[i];
if(is_valid(nx, ny, m, n)){
int child_cost = (movement[i] == graph[x][y])?cost:cost+1;
if(child_cost < node_cost[nx][ny]){
total_cost = min(total_cost, dfs(nx, ny, child_cost, m, n, graph, node_cost));
}
}
}
}

int Solution::solve(int m, int n, vector &C) {
vector<vector> node_cost(m, vector (n, INT_MAX));
int x = 0, y = 0, cost = 0;
return dfs(x, y, cost, m, n, C, node_cost);
}

#2

you should use the geeks for geeks method for applying dijktra’s on gird earlier i tried to do it by converting the grid into adjecency list representation for graph but passed test cases but in the end got MLE .
so i tried to look for efficient solution to this problem that doesn’t uses much extra space luckily GFG have that solution here’s the technique

#define ar array
int dx[4] = { 1 , -1 , 0 , 0 } ;
int dy[4] = { 0 , 0 , 1 , -1} ;
char dir[4] = { ‘D’ , ‘U’ , ‘R’ , ‘L’ };
int Solution::solve(int M , int N, vector &A) {

`````` int t[M][N] ;

for( int i = 0 ; i < M ; i++ )
for( int j = 0 ; j < N ; j++ )
t[i][j] = INT_MAX;

set< ar < int , 3 > > s ;

s.insert( { 0 , 0 , 0 } );
t[0][0] = 0 ;

while( !s.empty() )
{
auto x = *s.begin() ;
s.erase( s.find(x) );

int i = x[1] ; int j = x[2] ;

for( int p = 0 ; p < 4 ; p++ )
{
int a = i + dx[p] ;
int b = j + dy[p] ;

if( a < 0 || a >= M || b < 0 || b >= N )continue;
char y = A[i][j] ;

int c = y!=dir[p] ? 1 : 0 ;

if( t[a][b] > t[i][j] + c )
{
if( t[a][b] != INT_MAX )
{
s.erase( s.find( {t[a][b] , a , b} ) )  ;
}

t[a][b] = t[i][j] + c ;

s.insert( { t[a][b] , a , b } ) ;
}

}
}

return t[M-1][N-1] ;
``````

}