Connection Status:
Competition Arena > LongBlob

LongBlob

SRM 292 · 2006-03-06 · by dgoodman

SRM 292 · 2006-03-06 · by dgoodman · Graph Theory, Search
Class Name: LongBlob
Return Type: double
Method Name: maxLength
Arg Types: (vector<string>)
Problem Statement

Problem Statement

A satellite image consists of a rectangular grid of 1x1 squares, each having a value of 0 or 1. We want to identify the longest "blob", where a blob is a collection of 0's that are connected orthogonally. The length of a blob is defined to be the maximum Euclidean distance between the centers of any two 0's in the blob. For example, in the following image 
       0010
       1001
       0011
       0111
there are 2 blobs. The length of the big blob is sqrt(1+9), the distance between the 0 in the lower left corner and the one in row 0, column 1. The length of the tiny blob is 0.

The difficulty is that the image may contain some noise in the form of 1's that should be 0's. We do not want to underestimate the length of the longest blob. So we will consider all different ways of choosing up to 4 different 1's and replacing them with 0's. Among all these altered images we want the length of the longest blob.

Create a class LongBlob that contains a method maxLength that is given a String[] image and that return the length of the longest blob when up to 4 of the 1's in image are regarded as noise.

Notes

  • A return value with either an absolute or relative error of less than 1.0E-9 is considered correct.

Constraints

  • image will contain between 1 and 25 elements inclusive.
  • Each element of image will contain exactly n characters, where n is between 1 and 25 inclusive.
  • Each element of image will contain only the characters '0' (zero) and '1' (one).
Examples
0)
{"0010",
 "1001",
 "0011",
 "0111"}
Returns: 4.242640687119285

This is the example given above but now by replacing 4 1's with 0's we can get a blob that includes diagonally opposite corners. The distance between two opposite corners is sqrt(9 + 9).

1)
{"101010101"}
Returns: 7.0

Replace the first 4 1's with 0's. Then there is one long blob, whose length is the distance between the first 0 (that used to be a 1) and the last 0.

2)
{"011111111111111110",
 "011111111111011110",
 "111111111111111110"}
Returns: 5.0990195135927845
3)
{"011111111111111110",
 "011111111111010110",
 "111111111111111110"}
Returns: 6.082762530298219
4)
{"0000000000000000000000000","0000000000000000000000000","0000000000000000000000000","0000000000000000000000000","0000000000000000000000000","0000000000000000000000000","0000000000000000000000000","0000000000000000000000000","0000000000000000000000000","0000000000000000000000000","0000000000000000000000000","0000000000000000000000000","0000000000000000000000000","0000000000000000000000000","0000000000000000000000000","0000000000000000000000000","0000000000000000000000000","0000000000000000000000000","0000000000000000000000000","0000000000000000000000000","0000000000000000000000000","0000000000000000000000000","0000000000000000000000000","0000000000000000000000000","0000000000000000000000000"}
Returns: 33.94112549695428

Submissions are judged against all 83 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class LongBlob with a public method double maxLength(vector<string> image) · 83 test cases · 2 s / 256 MB per case

Submitting as anonymous