ImageCompress

TCCC '04 Round 3 · 2004-02-23 · by vorthys

TCCC '04 Round 3 · 2004-02-23 · by vorthys · Dynamic Programming, Recursion, String Manipulation

Show categories

Class Name: ImageCompress

Return Type: String

Method Name: compress

Arg Types: (vector<string>)

Problem Statement

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" }

Notes

Decompressing a compressed image requires knowledge of the original image's size, as well as the information in the format described here. Do not be concerned that the size is not encoded in the compressed format.

Constraints

image contains between 1 and 30 elements, inclusive.
Each element of image contains between 1 and 30 characters, inclusive.
Each element of image contains the same number of characters.
Every character in image is a 'B' or a 'W'.

Examples

{ "BBBWWW",
  "BBBWWW" }
Returns: "LBW"

The first example above. The left subimage is completely black, and the right subimage is completely white.

{ "BWB",
  "WWW" }
Returns: "CRBWW"

The second example above.

{ "BWBWBWBW",
  "WBWBWBWB",
  "BWBWBWBW",
  "WBWBWBWB",
  "BWBWBWBW" }
Returns: "CRBWRWB"

A checkerboard pattern.

{ "BBBBBWWWWWBBBBBWWWWWBBBBBWWWWW",
  "BBBBBWWWWWBBBBBWWWWWBBBBBWWWWW",
  "BBBBBWWWWWBBBBBWWWWWBBBBBWWWWW",
  "BBBBBWWWWWBBBBBWWWWWBBBBBWWWWW",
  "BBBBBWWWWWBBBBBWWWWWBBBBBWWWWW",
  "BBBBBWWWWWBBBBBWWWWWBBBBBWWWWW",
  "BBBBBWWWWWBBBBBWWWWWBBBBBWWWWW",
  "BBBBBWWWWWBBBBBWWWWWBBBBBWWWWW",
  "BBBBBWWWWWBBBBBWWWWWBBBBBWWWWW",
  "BBBBBWWWWWBBBBBWWWWWBBBBBWWWWW",
  "BBBBBWWWWWBBBBBWWWWWBBBBBWWWWW",
  "BBBBBWWWWWBBBBBWWWWWBBBBBWWWWW",
  "BBBBBWWWWWBBBBBWWWWWBBBBBWWWWW",
  "BBBBBWWWWWBBBBBWWWWWBBBBBWWWWW",
  "BBBBBWWWWWBBBBBWWWWWBBBBBWWWWW",
  "BBBBBWWWWWBBBBBWWWWWBBBBBWWWWW",
  "BBBBBWWWWWBBBBBWWWWWBBBBBWWWWW",
  "BBBBBWWWWWBBBBBWWWWWBBBBBWWWWW",
  "BBBBBWWWWWBBBBBWWWWWBBBBBWWWWW",
  "BBBBBWWWWWBBBBBWWWWWBBBBBWWWWW",
  "BBBBBWWWWWBBBBBWWWWWBBBBBWWWWW",
  "BBBBBWWWWWBBBBBWWWWWBBBBBWWWWW",
  "BBBBBWWWWWBBBBBWWWWWBBBBBWWWWW",
  "BBBBBWWWWWBBBBBWWWWWBBBBBWWWWW",
  "BBBBBWWWWWBBBBBWWWWWBBBBBWWWWW",
  "BBBBBWWWWWBBBBBWWWWWBBBBBWWWWW",
  "BBBBBWWWWWBBBBBWWWWWBBBBBWWWWW",
  "BBBBBWWWWWBBBBBWWWWWBBBBBWWWWW",
  "BBBBBWWWWWBBBBBWWWWWBBBBBWWWWW",
  "BBBBBWWWWWBBBBBWWWWWBBBBBWWWWW" }
Returns: "LLLBCCBWWLLWBBLLWCCWBBLLBWW"

{ "BBBWWW", "WWWBBB", "BBWWBB" }
Returns: "RRLBWCCBWCBWLWB"

{ "WWBWBWBW",
  "WBWBWBWB",
  "BWBWBWBW",
  "WBWBWBWB",
  "BWBWBWBB" }
Returns: "CRCCRRWBBBBWRCWCWUWBB"

Another checkerboard, but with the upper left and lower right corners swapped.

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

Coding Area

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