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:
Output:
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 asked 03 Jan '15, 14:34
