# find largest island area using dfs

Given a 2D matrix filled with 0 and 1, where 0 represents water and 1 represents a land. find largest island area using dfs. An island is defined as a group of connected 1s. For example let see below figure.

From the above figure it is clear that we need to find 8 connections around a point (u,v). we need search 8 neighbors of matrix’s pth row and vth column.

*using helper array dx[] and dy[] , we can search valid neighbors of point u,v.**Initial make every cell of matrix visited.**Run dfs from the matrix cell , where there is map[i][j] == 1.**Search all valid 8 neighbors and make them visited.*

*Sample code find largest island area using dfs*

#include <iostream> #include<string.h> using namespace std; #define row 6 #define col 9 int map[row][col] = { { 0, 1, 1, 1, 1, 0, 0, 0, 0 }, { 1, 0, 1, 1, 1, 0, 0, 1, 1 }, { 0, 1, 1, 1, 0, 0, 1, 1, 1 }, { 0, 1, 1, 0, 0, 0, 1, 0, 1 }, { 0, 0, 0, 0, 1, 0, 0, 0, 0 }, { 0, 1, 1, 1, 0, 0, 1, 1, 0 } }; int visited[row][col]; int max_area = 0; // 8 component int dx[] = { -1, -1, -1, 0, 0, 1, 1, 1 }; int dy[] = { -1, 0, 1, -1, 1, -1, 0, 1 }; void dfs(int u, int v) { if (!visited[u][v]) { visited[u][v] = 1; max_area++; } // search for 8 neighbours for (int i = 0; i < 8; i++) { int x = u + dx[i]; int y = v + dy[i]; if (x < 0 || x >= row || y < 0 || y >= col) { continue; } if (visited[x][y] || map[x][y] == 0) continue; visited[x][y] = 1; max_area++; dfs(x,y); } } int main() { memset(visited, 0, sizeof(visited)); int Ans = 0; for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { if (map[i][j] && !visited[i][j]) { dfs(i, j); if (Ans < max_area) { Ans = max_area; } max_area = 0; } } } cout << "Maximum Island Area is " << Ans << endl; return 0; }

**Output**

**Output**

*Maximum Island Area is 13*

## Leave a Reply