Your task is to convert a black-and-white image into the compressed format described below.
Your method should return the shortest possible encoding for the image. If more than
one encoding achieves the minimum length, return the one that comes first alphabetically.
The encoding format is based on the idea of recursively decomposing an image into subimages
until each subimage is composed of a single color. For example, the image
BBBWWW
BBBWWW
might be decomposed into two 2-by-3 subimages:
BBB WWW
BBB WWW
The black subimage could then be encoded as 'B' and the white subimage could be encoded as 'W'.
The entire decomposition would be encoded as "LBW".
An image can be decomposed in four different ways, each indicated by a single character:
- 'L' indicates that the image is decomposed into its left half and its right half (if the
image contains an odd number of columns, the center column is considered part of the left half).
- 'U' indicates that the image is decomposed into its upper half and its lower half (if
the image contains an odd number of rows, the center row is considered part of the upper half).
- 'C' indicates that the image is decomposed into even columns and odd columns (the leftmost
column is considered column 0, and is therefore even).
- 'R' indicates that the image is decomposed into even rows and odd rows (the topmost row
is considered row 0, and is therefore even).
The letters 'B' and 'W' indicate that the image is completely black or completely
white, respectively. If the image contains a mix of black and white, then it is decomposed in one of the four
ways. The image is encoded as the single letter for the decomposition pattern, followed by the encoding of the
left/upper/even subimage, followed by the encoding of the right/lower/odd subimage. An image that contains a single
column will never be decomposed using 'L' or 'C', and an image that contains a
single row will never be decomposed using 'U' or 'R'.
For example, the image
BWB
WWW
could be encoded in a minimum of 5 characters in any of the following ways: "CRBWW", "CUBWW", "RCBWW", or
"UCBWW". Of these, "CRBWW" is the first alphabetically, so it is the preferred answer. The 'C'
indicates that the original image is decomposed into the two subimages
BB W
WW W
The 2-by-2 subimage is then encoded as "RBW" and the all-white 2-by-1 subimage is encoded simply as 'W'.
The image will be given as a rectangular String[] image containing the characters 'B' and 'W'.
Each element of image represents a row of the image. For example, the image
BBBWWW
WWWBBB
BBWWBB
would be represented as
{ "BBBWWW", "WWWBBB", "BBWWBB" }
|