ImageCompression | Topcoder Archive

Problem Statement

You have a rectangular bitmap that consists of n rows by m columns of pixels. You are given the bitmap encoded as a String[] image. Each pixel of the bitmap is either black or white. Black pixels are represented by the character '0', white ones by '1'.

You are also given an int k that divides both n and m. You want to check whether you can compress the bitmap by shrinking it k times in each dimension. More precisely, the compression works as follows:

Divide the bitmap into blocks of size k times k pixels.
Check whether each block consists of pixels of a single color only. If some block contains both black and white pixels, the bitmap cannot be compressed.
Compress the bitmap by shrinking each block into a single pixel of the respective color.

Determine whether we can compress the given bitmap for the given k. If we can, return "Possible", otherwise, return "Impossible". Note that the return value is case-sensitive.

Definition

Class:: ImageCompression
Method:: isPossible
Parameters:: String[], int
Returns:: String
Method signature:: String isPossible(String[] image, int k)
(be sure your method is public)

Constraints

n,m will be between 2 and 50, inclusive.
image will contain exactly n elements.
Each element of image will contain exactly m characters.
Each character of each element of image will be '0' or '1'.
k will be between 2 and 50.
k will divide n and m.

Examples

{
"0011",
"0011",
"1100",
"1100",
"0000",
"0000"
}

Returns: "Possible"

```
{
"0011",
"0011",
"1100",
"1100",
"0010",
"0000"
}
```
```
2
```
```
Returns: "Impossible"
```
The block in the bottom right corner contains three black pixels and one white pixel.

{
"111000111",
"111000111",
"111000111"
}

Returns: "Possible"

{
"001100",
"001100",
"110011",
"110011",
"001100",
"001100"
}

Returns: "Impossible"

This is not compressible when k=6.

{
"001100",
"001100",
"110011",
"110011",
"001100",
"001100"
}

Returns: "Possible"

It is compressible when k=2 however.

{
"11111111",
"11111111",
"11111111",
"11111111",
"11111111",
"11111111",
"11111111",
"11111111"
}

Returns: "Possible"

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.