Find the number of islands

 Given a grid consisting of '0's(Water) and '1's(Land). Find the number of islands.

Note: An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically or diagonally i,e in all 8 directions.
 

Example 1:

Input:
grid = {{0,1},{1,0},{1,1},{1,0}}
Output:
1
Explanation:
The grid is-
0 1
1 0
1 1
1 0
All lands are connected.

Example 2:

Input:
grid = {{0,1,1,1,0,0,0},{0,0,1,1,0,1,0}}
Output:
2
Expanation:
The grid is-
0 1 1 1 0 0 0
0 0 1 1 0 1 0 
There are two islands one is colored in blue 
and other in orange.

 

method:

finding the no. of connected components in the grid is same as Connected Components in an undirected graph

also check how to find depth first search in grid DFS on a 2D array/2D grid

here we have to use all 8 direction around a cell

c++ implementation: using arrays

#include<bits/stdc++.h>
using namespace std;
int n ;int m;
int vis[1001][1001];
int grid[1001][1001];
int dx[8]={-1,-1,-1,0,0,1,1,1};
int dy[8]={-1,0,1,-1,1,-1,0,1};

void dfs(int x,int y)
{
     
    vis[x][y]=1;
for (int i=0;i<8;i++)
{ int u=x+dx[i];int v=y+dy[i];
if(u>=0 && u<n && v>=0 && v<m && vis[u][v]==0 && grid[u][v]==1)
        dfs(u,v);
}
}


int main(){
	int t; // no. of test cases
	cin>>t;
	
	while(t--)
	{
		cin >> n >> m;
		
		
		for(int i = 0; i < n; i++)
                {
			for(int j = 0; j < m; j++)
                        {
				cin >> grid[i][j];
				vis[i][j]=0;
			}
		}
			int c=0; //for counting 
		for(int i = 0; i < n; i++)
               {
			for(int j = 0; j < m; j++)
                        {
				if(vis[i][j]==0 && grid[i][j]==1)
				{
				    dfs(i,j);
				    c++;
				}
			}
		}
	
             cout<<c<<" ";
	}
} 

 

• Time complexity: O(V + E), where V is the number of vertices and E is the number of edges in the graph.
• Space Complexity :O(V). 

c++ implementation: using vectors

#include<bits/stdc++.h>
using namespace std;

 // } Driver Code Ends
class Solution {
public:
//the main number of island program starts here

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

void dfs(vector<vector<char>>&A,vector<vector<int>> &vis,int x,int y,int N,int M)
{ 
   vis[x][y]=1;
for (int i=0;i<8;i++)
{ int u=x+dx[i];int v=y+dy[i];
if(u>=0 && u<N && v>=0 && v<M && vis[u][v]==0 && A[u][v]=='1')
        dfs(A,vis,u,v,N,M);
}    
}


int numIslands(vector<vector<char>>& A){
int count=0;
int N=A.size();
int M=A[0].size();
vector<vector<int>> vis(N,vector<int> (M,0));
 
 for(int i=0;i<N;i++)
 {for(int j=0;j<M;j++)
   { if(vis[i][j]==0 && A[i][j]=='1')
    {dfs(A,vis,i,j,N,M);
    count++;}}
 }
 return count;
}
//ends here
};


// { Driver Code Starts.
int main(){
	int tc;
	cin >> tc;
	while(tc--){
		int n, m;
		cin >> n >> m;
		vector<vector<char>>grid(n, vector<char>(m, '#'));
		for(int i = 0; i < n; i++){
			for(int j = 0; j < m; j++){
				cin >> grid[i][j];
			}
		}
		Solution obj;
		int ans = obj.numIslands(grid);
		cout << ans <<'\n';
	}
	return 0;
}  // } Driver Code Ends

• Time complexity: O(V + E), where V is the number of vertices and E is the number of edges in the graph.
• Space Complexity :O(V).