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

### Definition

 Class: ImageCompress Method: compress Parameters: String[] Returns: String Method signature: String compress(String[] image) (be sure your method is public)

### 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

0)

 ```{ "BBBWWW", "BBBWWW" }```
`Returns: "LBW"`
 The first example above. The left subimage is completely black, and the right subimage is completely white.
1)

 ```{ "BWB", "WWW" }```
`Returns: "CRBWW"`
 The second example above.
2)

 ```{ "BWBWBWBW", "WBWBWBWB", "BWBWBWBW", "WBWBWBWB", "BWBWBWBW" }```
`Returns: "CRBWRWB"`
 A checkerboard pattern.
3)

 ```{ "WWBWBWBW", "WBWBWBWB", "BWBWBWBW", "WBWBWBWB", "BWBWBWBB" }```
`Returns: "CRCCRRWBBBBWRCWCWUWBB"`
 Another checkerboard, but with the upper left and lower right corners swapped.
4)

 ```{ "WWWWWWWWWW", "WWBBWWBBWW", "WBBBBBBBBW", "WBBBBBBBBW", "WWBBBBBBWW", "WWWBBBBWWW", "WWWWBBWWWW", "WWWWWWWWWW" }```
`Returns: "UURWCCWBCWBCCCCWBBBCLBWBRCCCWBRBWCCWBRBWRLLWBLLBWWW"`

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=2326

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=5008&pm=2326

vorthys

#### Testers:

lbackstrom , brett1479

#### Problem categories:

Dynamic Programming, Recursion, String Manipulation