One Boolean Matrix of n rows and m columns is given, we have find the largest islands from it including water which may or may not be surrounded by the land.
:
1 represents land, 0 represents water
Example
0 0 0 0 0 0
0 1 1 1 1 1
0 1 0 0 0 1
0 1 1 1 0 1
0 1 1 1 1 1
output: 20
you can consider inside water as a pond water on the island
Can someone provide me the solution for this problem?
Assuming water body is surrounded on all 4 sides.
You can do a quick dfs for all land bodies and store their size. Then do a dfs for all water bodies and check that its surrounded by land and also store the group of this corresponding land. Then answer is the max of all (size of water body + size of corresponding landmass).
One possible approach could be to run a dfs from all the boundary points where its value is 0 and convert that to 2. And now for the nodes whose value is not 2 find out the maximum size of the component and that will be the answer.
By boundary points, I meant to say the extreme points. Like the points in the first row and in the last row and in the first column and the last column.
So for this,
0 0 0 0 0 0
0 1 1 1 1 1
0 1 0 0 0 1
0 1 1 1 0 1
0 1 1 1 1 1
It will become,
2 2 2 2 2 2
2 1 1 1 1 1
2 1 0 0 0 1
2 1 1 1 0 1
2 1 1 1 1 1
Now run the dfs for the points whose value is not 2 and find out the maximum sized component.
Can you provide me the code for the same? I am not getting, how to store corresponding land thing!!
This is a pretty similar question. For water islands, you can just convert all 0’s to 1’s and just compare the maximum of 1-Islands and 0-Islands
Use a map and store the size of all landmasses with a counter. Each time you dfs increment the counter