0

I am getting TLE in the question find no of the island. link to the question - https://practice.geeksforgeeks.org/problems/find-the-number-of-islands/1/?track=md-graph&batchId=144 My approach is to simply use DFS and find components(land) starting from land and calculate the no of the component and return. Here is my code

#include<bits/stdc++.h>
using namespace std;
bool issafe(int i,int j ,int n,int m, vector<vector<char>>graph)
{
  if(i<0 || i>n-1 || j<0 || j>m-1 || graph[i][j]=='0')
  return false;
  return true;
}
void DFS(int u,int v, vector<vector<char>>& grid,int n,int m,vector<vector<int>>& vis)
{
  static int row[]={-1,0,0,1,-1,-1,1,1 };//up,left,right,down, upper left, upper, right, lower left, lower right;
  static int col[]={0,-1,1,0,-1,1,-1,1 };
  vis[u][v]=1;
  for(int k=0;k<8;k++)
  {
    if(issafe(u+row[k],v+col[k],n,m,grid) && !vis[u+row[k]][v+col[k]] )
    {
      DFS(u+row[k], v+col[k], grid, n, m, vis);
    }
  }
}
int numIslands(vector<vector<char>>& grid)
{
  int n=grid.size(),m=grid[0].size();
  vector<vector<int>>vis(n,vector<int>(m,0));
  int ans=0;
  for(int i=0;i<n;i++)
  {
    for(int j=0;j<m;j++)
    {
      if(vis[i][j]==0 && grid[i][j]!='0')
      {
        DFS(i,j,grid,n,m,vis);
        ans++;
      }
    }
  }
  return ans; 
}
Some programmer dude
  • 400,186
  • 35
  • 402
  • 621
Raj verma
  • 1
  • 1
  • 2
    Please don't use so-called "competition" sites as a learning or teaching resource, because they are *not* that. Not unless all you ever want to learn are truly bad habits and code. So bad that it can make you practically unemployable. Get [some good books](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list) to read, and take classes instead. – Some programmer dude May 29 '21 at 10:05
  • Note: for each call of `issafe`, `graph` is copied each time. Use a reference `&graph` instead. – Damien May 29 '21 at 10:24
  • Try writing iterative solution. The time limit is very tight and 3 of my recursive codes failed. Finally the iterative code passed. – risingStark May 29 '21 at 10:57

1 Answers1

1

One change is that you don't want to have an extra space to mark the visited or not visited. We can do it in grid itself by marking it as say grid[i][j] = '0'.

class Solution
{
    public:
    //Function to find the number of islands.
     int numIslands(vector<vector<char>>& grid) {
        if (grid.size() == 0)
            return 0;
        int islands = 0;
        int row = grid.size();
        int col = grid[0].size();
        for (int i=0; i<row; i++) {
            for (int j=0; j<col; j++) {
                if (grid[i][j] == '1')
                islands += helper(grid, i, j);
            }
        }
        return islands;
    }
    
    int helper(vector<vector<char>>& grid, int i, int j) {
        if (i<0 || j<0 || i>=grid.size() || j>=grid[0].size() || grid[i][j] == '0')
            return 0;
        grid[i][j] = '0';
        helper(grid, i, j-1);
        helper(grid, i, j+1);
        helper(grid, i-1, j);
        helper(grid, i+1, j);
        helper(grid, i+1, j+1);
        helper(grid, i+1, j-1);
        helper(grid, i-1, j+1);
        helper(grid, i-1, j-1);
        return 1;
    }
};

This is an accepted version for the number of islands.

Rohith V
  • 1,089
  • 1
  • 9
  • 23