Getting MLE on DFS solution. Please help


#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));
}
}
}
return total_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] ; 

}