ZOJ Problem Set - 3215
Cartoon is a form of visual art and illustration. It contains visual work for print media, for electronic media, and even animated films and animated digital media. Cartoon usually use simple and exaggerated rather than realistic technoque to express the characters and scenarios. Instead of exquisite gradient effect, large areas of color blocks are more offen used in catoons.
Though the pictures above look rather different, we can still recognize they are the same person. For we can recognize the same features from the pictures, e.g. the hair is black and the skin is pink. Now your task is similar, to make a picture looks like cartoon.
To simplify the problem, the format of the pictures to be deal with is in grey scale, not in RGB color. What's more, we formally define the differnece of two pictures of the same size by the following equation:
where I(i, j) and I'(i, j) are the colors of pixels in (i, j) in the two picture. You are asked to modify a picture so that the result picture contains no more than K colors, and the difference after modification is minimum.
The first line of the input is an integer T (T <= 50), the number of cases.
The first line of each test case contain three integers N, M and K, (0 < N, M, K <= 50), indicating the height and the width of the picture, and the maximum number of colors in the result picture. The following N lines each contains M integers in the range [0, 65535], indicating the grey scale in each pixel.
For each test case, output the minimum difference after modification rounded to 0.01.
1 3 5 2 10 10 10 10 10 10 1 10 2 10 10 10 10 10 10
Change the colors in (2, 2) and (2, 4) into 1.5 will get the result.
Author: GUAN, Yao
Source: ZOJ Monthly, June 2009