Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Object detection is a computer vision technique that is used to identify and locate objects in an image. An image can be considered as a 2D array containing $P$ rows and $Q$ columns. Each element at position $(i, j)$ in the image is called a ‘picture element’ or pixel. In this problem, we will only consider Grayscale Images, which means, each pixel can be described by a single value denoting the intensity (amount of light) of that pixel. Let’s denote a $N\times M$ sub-image (where $1\leq N \leq P$ and $1 \leq M \leq Q$) of the image to be a rectangle in the image containing $N$ rows and $M$ columns.

You will be given an image containing $R$ rows and $C$ columns, and an object image containing $X$ rows and $Y$ columns $(X \leq R, \, Y \leq C)$. Your task is to find out an $X\times Y$ sub-image of the given image that has the smallest distance from the object image. To calculate the distance, you need to sum up the squared difference between the intensity of each pixel of the object image and its corresponding pixel in the sub-image. For the sub-image positioned at $i$th row and $j$th column of the original image, we can calculate the distance using:

$\text{Distance}_{ij} = \sum\limits_{p=0}^{x-1}\sum\limits_{q=0}^{y-1}\left(A_{(i+p)(j+q)}-B_{(p+1)(q+1)}\right)^2$,

where $A$ is the original image and $B$ is the object that we are looking for.

The first line of the input contains a single integer $T (1 \leq T \leq 5)$, denoting the number of test cases.

The following line contains two space-separated integers $R$ and $C (1 \leq R, \, C \leq 500)$, denoting the number of rows and the number of columns in the original image, respectively. The following $R$ lines each contain $C$ space-separated integers, describing each pixel’s intensity in the original image.

The next line contains two space-separated integers $X (1 \leq X \leq R)$ and $Y (1 \leq Y \leq C)$, denoting the number of rows and the number of columns in the object image, respectively. The following $X$ lines each contain $Y$ space-separated integers, describing each pixel’s intensity in the object image.

The intensity value of each pixel will be in the range $[0, 50]$.

Print two space-separated integers $x \, \, y$ denoting the index of the top-left corner of the sub-image that meets the criteria. If there are multiple grids with the smallest distance, print the lexicographically smallest $x \, \, y$. That means if there are multiple grids that meet the criteria, print the one with the smallest $x$. If there are multiple grids with the smallest $x$ that meet the criteria, print the one with the smallest $y$.

Assume that the indices are 1-indexed.

Input | Output |
---|---|

1 3 3 1 2 3 4 4 5 6 7 8 1 1 4 | 2 1 |

Toph uses cookies. By continuing you agree to our Cookie Policy.