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

Output

Maximum Island Area is 13




Related Contents to follow