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.

find largest island area using dfsFrom 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

Maximum Island Area is 13



Related Contents to follow