A message received from a satellite sent on Jupiter contains the
information about which part of the concerned area is land and which is a
part of ocean. To do this, the satellite divides the whole rectangular
area into small squares of unit dimensions and for each square cell, it
sends a terrain bit (either ‘0 or ‘1’) telling whether that square is a
part of land or a part of a water body. ‘0’ for a square tells that it
is a land and ‘1’ tells that it is a part of water body.
Given
the terrain bit for each square cell, you have to decide the size of
largest island on the area considered so that it can decide where to
land.
If two cells have terrain bit as ‘0’ and they have a common side,
they belong to same island.
Input/Output Specifications
Input:
Size of the rectangular area {N,M)
Message: ( N lines each containing M bits)
Output:
Size of largest useful land
Method / Formula:
Max_size = 0
while there is at least one unvisited land cell
{
Pick an unvisited cell (call it current cell)
Put the current cell into the visiting queue.
Local_size = 0
While the visiting queue is not empty:
{
Pick a cell from the visiting queue
Mark the current cell as visited;
Put all the unvisited neighboring cells of ‘x’ (which are already not in the queue) into the visiting queue q;
Increase local_size by 1;
}
If (local_size > size) then size = local_size;
}
Examples
Example 1
Size of the area ={1,1}
Message(encoded bits) = {1}
O/P = 0
Example 2
Size of the area ={2,2}
Message(encoded bits) = {1#0,0#1}
O/P = 1
Example 3
For a given message for a 3*9 rectangular field as follows:
011010001
010100000
111110011
The largest useful land size is 10