I I U P C 2 0 1 3

Problem D: Dilation

Sabbir is a student of fourth year in CSE department. His course teacher recently gave him an assignment that is discussed below. But he is a little bit weak in programming. So, he needs your help to solve the problem. Morphological image processing is a collection of non-linear operations related to the shape or morphology of features in an image. One of the most basic morphological operations is dilation. Dilation adds pixels to the boundaries of objects in an image. The number of pixels added to the objects in an image depends on the size and shape of the structuring element used to process the image. A structuring element is a shape mask used in the basic morphological operations. They can be of any shape and size that is digitally representable, and each has an origin. The matrix dimensions specify the size of the structuring element and the pattern of ones and zeros specifies the shape of the structuring element.  In this task the size of the structuring element is square i.e. 2×2, 3×3, or 4×4 etc. and can be of any shape. The morphological functions use the following code to get the coordinates of the origin of structuring elements of any size and dimension. origin = floor(size(structuring_element)/2) If structuring element matrix is [0 1 0; 1 1 1; 0 1 0] Then, size(structuring_element)= 3×3 So, origin = (1,1) [i.e. see the following figure] Dilate (B,S) takes binary image B, places the origin of the structuring element S over each 1-pixel, and ORs the structuring element S into the output image at the corresponding position.
Input
First line of the input file is an integer T (T < 25) which denotes how many sets of inputs are there. Each test case starts with the dimensions of the binary image m×n where m (2 ≤ m ≤ 100) is the number of rows and n (2 ≤ n ≤ 100) is the number of columns. Followed by the binary image which contains only 0 or 1. Then followed by the dimensions of the structuring element q×r where q (1 ≤ q ≤ 10) is the number of rows and r (1 ≤ r ≤ 10) is the number of columns and then followed by the structuring element. Size of structuring element will be less than or equal to binary image (q ≤ n, r ≤ m). In input binary image border lines will not contain any 1’s.
Output
For each test case print the binary image after dilation process. N.B: In output there will be no blank space (“ ”) after the end of a line.
Sample Input	Output for Sample Input
2 3 4 0 0 0 0 0 1 1 0 0 0 0 0 3 3 0 1 0 1 1 1 0 1 0 4 4 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 3 3 1 1 1 1 1 1 1 1 1	Case 1: 0 1 1 0 1 1 1 1 0 1 1 0 Case 2: 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1

Problem Setter : Md. Azher Uddin

Alternate Solution : Tanveer Ahsan