Kind of a Blur#1279
Blurring of an image occurs when the object being photographed is out of the camera's focus. The top two figures on the right show an example of an image and its blurred version. Reconstructing the original image given only the blurred version is one of the most interesting topics in image processing. This process is called deblurring, which is your task in this problem.
In this problem, all images are grayscale (without colors). Images are represented as a rectangular matrix of real numbers, where each cell corresponds to the brightness of the respective pixel. Although not mathematically strict, one way to model a blurred image is to replace every pixel with the average of all pixels within a given Manhattan distance (including the pixel itself). Here is an illustration of how to compute the blurring of a 3 \times 3 image with a blurring distance of :
Given the blurred version of an image, your goal is to reconstruct the original image, assuming the blurring was performed as described above.
The input consists of several test cases. Each test case is given in H + 1 lines. The first line contains three non-negative integers: the width , height of the blurred image, and the blurring distance , where 1 \leq W, H \leq 10 and D \leq \min \left( \frac{W}{2}, \frac{H}{2} \right). The next lines describe the blurred image: each line contains non-negative real numbers, each specified with up to decimal places. All real numbers in the input are less than .
Zero or more blank lines (consisting only of whitespace) may appear between test cases. The last line of the input file consists of three zeros.
For each test case, print a W \times H matrix of real numbers representing the deblurred image. Each element must be rounded to exactly decimal places and right-justified in a field of width . Separate the outputs of consecutive test cases with a blank line. Do not print a blank line after the last test case. It is guaranteed that there exists exactly one unique solution for each test case.
Example 1