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. | |||||||||||||
Definition | |||||||||||||
| |||||||||||||
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) | |||||||||||||
| |||||||||||||
| 1) | |||||||||||||
| |||||||||||||
| 2) | |||||||||||||
| |||||||||||||
| 3) | |||||||||||||
| |||||||||||||