coder_of_india.'s blog

By coder_of_india., history, 15 months ago, In English

*****************************************************TLE CODE *************************************************************

int dx[4] = {0 , -1 , 0 , 1} ; . int dy[4] = {-1 , 0 , 1 , 0} ;
``````
bool checker (vector<vector> grid , int i , int j , int n , int m )
{
if(i >= 0 && i < n && j >= 0 && j < m && ( grid[i][j] == '1'))
return true;
return false;
}

void dfs(vector<vector> &grid , int i , int j ,int r , int c) {

grid[i][j] = '0';
for(int k = 0 ; k < 4 ; k ++ )
{
    int newx = i + dx[k] ;
    int newy = j + dy[k] ;
    if( checker(grid , newx , newy , r , c)  ) 
    {    
        grid[newx][newy] = '0';
        dfs(grid , newx , newy , r , c);
    }
}

} class Solution { public: int numIslands(vector<vector>& grid) {

int r = grid.size() ;
    int c = grid[0].size() ;
    int cnt = 0 ;
    for(int i = 0 ; i < r ; i ++ )
    {
        for(int j = 0 ; j < c ; j ++ ) 
        {
              if(grid[i][j] == '1') 
              {
                  cnt ++ ; 
                  dfs(grid , i , j ,r , c);
              }
        }
    }
    return cnt ;
}

};

************************************************** AC CODE *******************************************************************

int dx[4] = {0 , -1 , 0 , 1} ; int dy[4] = {-1 , 0 , 1 , 0} ;

void dfs(vector<vector> &grid , int i , int j ,int r , int c) {

grid[i][j] = '0';
for(int k = 0 ; k < 4 ; k ++ )
{
    int newx = i + dx[k] ;
    int newy = j + dy[k] ;
    if(newx >= 0 && newx < r && newy >= 0 && newy < c && ( grid[newx][newy] == '1')) 
    {    
        grid[newx][newy] = '0';
        dfs(grid , newx , newy , r , c);
    }
}

} class Solution { public: int numIslands(vector<vector>& grid) {

int r = grid.size() ;
    int c = grid[0].size() ;
    int cnt = 0 ;
    for(int i = 0 ; i < r ; i ++ )
    {
        for(int j = 0 ; j < c ; j ++ ) 
        {
              if(grid[i][j] == '1') 
              {
                  cnt ++ ; 
                  dfs(grid , i , j ,r , c);
              }
        }
    }
    return cnt ;
}

}; ******************************************************************************************************************************

Both codes are same but there is one difference I used cheacker function that's why i am getting tle why this is happening ? please tell me anyone.

Thanks in advance !!

 
 
 
 
  • Vote: I like it
  • -12
  • Vote: I do not like it

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by coder_of_india. (previous revision, new revision, compare).

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by coder_of_india. (previous revision, new revision, compare).

»
15 months ago, # |
  Vote: I like it +5 Vote: I do not like it

1) Plz, use spoiler tag or smth to more readable code in blogs.

bool readable = false;

2) Your checker function copying vector. You need to use reference to vector instead of copy;

bool checker(vector<vector>& grid, int i, int j, int n, int m)
  • »
    »
    15 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you ! it is working But why copying vector is cause of tle ??

    • »
      »
      »
      15 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      copying the vector takes the whole memory in function call but calling by reference only takes the address which is more sufficient than whole vector and its also very powerful method in c++..