Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

ANARC09I - Kind of a blur

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/anarc09i


Origin and Blured Image

Image blurring occurs when the object being captured is out of the camera’s focus. The top two figures on the right are an example of an image and its blurred version. Restoring the original image given only the blurred version is one of the most interesting topics in image processing. This process is called deblurring, which will be your task for this problem.


In this problem, all images are in grey-scale (no colours). Images are represented as a 2 dimensional matrix of real numbers, where each cell corresponds to the  brightness of the corresponding pixel. Although not mathematically accurate, one way to describe a blurred image is through averaging all the pixels that are within (less than or equal to) a certain Manhattan distance† from each pixel (including the pixel itself ). Here’s an example of how to calculate the blurring of a 3x3 image with a  blurring distance of 1:

How to compute

Mahattan distance

Given the blurred version of an image, we are interested in reconstructing the original version assuming that the image was blurred as explained above.

Input

Input consists of several test cases. Each case is specified on H + 1 lines. The first line specifies three non negative integers specifying the width W , the height H of the blurred image and the blurring distance D respectively where (1 ≤ W, H ≤ 10) and (D ≤ min(W/2, H/2)). The remaining H lines specify the gray-level of each pixel in the blurred image. Each line specifies W non-negative real numbers given up to the 2nd decimal place. The value of all the given real numbers will be less than 100. Zero or more lines (made entirely of white spaces) may appear between cases. The last line of the input file consists of three zeros.

Output

For each test case, print a W × H matrix of real numbers specifying the deblurred version of the image. Each element in the matrix should be approximated to 2 decimal places and right justified in a field of width 8. Separate the output of each two consecutive test cases by an empty line. Do not print an empty line after the last test case. It is guaranteed that there is exactly one unique solution for every test case.

Example

Input:
2 2 1
1 1
1 1
3 3 1
19 14 20
12 15 18
13 14 16
4 4 2
14 15 14 15
14 15 14 15
14 15 14 15
14 15 14 15
0 0 0

Output:
1.00 1.00
1.00 1.00

2.00 30.00 17.00
25.00 7.00 13.00
14.00 0.00 35.00

1.00 27.00 2.00 28.00
21.00 12.00 17.00 8.00
21.00 12.00 17.00 8.00
1.00 27.00 2.00 28.00

Được gửi lên bởi:Race with time
Ngày:2010-11-08
Thời gian chạy:1.435s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:ACM ANARC 2009

hide comments
2016-09-24 15:43:21
Code AC:
http://shink.in/zp4aQ
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.