
ZOJ Problem Set  3335
Median filtering is a common method in image processing. It is particularly useful to reduce speckle noise and pepper noise. Its edgepreserving nature makes it useful in cases where edge blurring is undesirable. Median filtering is defined as follow. Let X be the matrix represents an image, and the matrix's size is p * q. The coordinate of the matrix's top left element is (1, 1). The result of the median filtering with an m * n (where m, n are both odd integers) rectangle window is also a matrix Y. The window scan the image from left to right and from top to bottom. We defined the new matrix as follow: For each (i, j) where 1 <= i <= n and 1 <= j <= m,
For example, if the window's size is 3 * 3 and the matrix X is: 1 2 3 3 2 1 4 2 3 3 2 5 6 2 3 3 2 1 4 2 3 3 2 7 1 4 5 6 7 8 1 1 2 3 4 then the new matrix Y will be: 1 2 3 3 2 1 2 3 3 3 2 2 3 3 3 3 3 3 2 2 3 3 4 4 1 4 3 3 4 8 1 1 2 3 4 Now you are given the matrix X, and your task is to calculate the matrix Y. Input There are multicases. In the first line, there are two numbers p and q (1 <= p, q <= 500), which indicate the size of matrix X. Follow p lines, and each line has q integers, which are all in range [0, 255]. There are two integers m, n (1 <= m, n <= 49, p >= m, q >= n, and m, n are odd integers. ) in the last line, which indicate the window's size. There is a line between cases. Output You should output the matrix Y. Print a line after each case. Sample Input 5 5 1 2 3 3 2 1 4 2 3 3 2 5 6 2 3 3 2 1 4 2 3 3 2 7 1 3 3 7 5 1 2 3 3 2 1 4 2 3 3 2 5 6 2 3 3 2 1 4 2 3 3 2 7 1 4 5 6 7 8 1 1 2 3 4 3 3 Sample Output 1 2 3 3 2 1 2 3 3 3 2 2 3 3 3 3 3 3 2 2 3 3 2 7 1 1 2 3 3 2 1 2 3 3 3 2 2 3 3 3 3 3 3 2 2 3 3 4 4 1 4 3 3 4 8 1 1 2 3 4 Author: LIN, Yue Source: ZOJ Monthly, May 2010 