You are not logged in. Please login at www.codechef.com to post your questions!

×

Satellite Problem

    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

asked 03 Jan '15, 14:34

manisatwick's gravatar image

0★manisatwick
11
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,918
×1,491
×1,314

question asked: 03 Jan '15, 14:34

question was seen: 2,253 times

last updated: 03 Jan '15, 14:34