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 Endsclass 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).

darkmode