50005. Pattern Recognition

I'm a slow walker, but I never walk backwards.

Problem Description

Write a program to recognize a $k$ by $k$ pattern in an $n$ by $n$ matrix. Both the matrix and the pattern consist of integers. A submatrix of the matrix matches the pattern if the following are true.

  • There are no more than $m$ mismatch among the numbers.
  • The sums of the numbers in the two matrices differ no more than $d$.

For example the following pattern is a match of the following submatrix if $m$ is $2$, and $d$ is $2$. However, they do not match when either $m$ is $1$, or $d$ is $1$.

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

Now given the matrix, the pattern, $k$, and $d$, please report the position of upper-left corner of the last match. Here we assume that the first row is at the top and the first column is on the left. The last match is the match that has largest row index with its upper left corner element. If there are more than one match in that row, report the one with the largest column index. All indices start from 0.

In some subtasks there could be no match. In that case report -1 -1.

Subtasks

  • 20pt. $n$ is between $1$ and $10$, $k$ is $1$, $m$ is $0$, $d$ is $0$, and there is always a match. That is, you only need to check where the last pattern is.
  • 20pt. $n$ is between $1$ and $10$, $k$ is between $1$ and $n$, $m$ is between $1$ and $k \times k$, $d$ is extremely large so you do not to care about it, and there is always a match.
  • 30pt. $n$ is between $1$ and $10$, $k$ is between $1$ and $n$, $m$ is between $1$ and $k \times k$, $d$ is positive, and there is always a match.
  • 30pt. $n$ is between $1$ and $10$, $k$ is between $1$ and $n$, $m$ is between $1$ and $k \times k$, $d$ is positive, and there could be no match.

Input Format

The first line contains four integers $n$, $k$, $m$, $d$. The next $n$ lines has the matrix and $n$ elements in each line. The next $k$ lines has the pattern and $k$ elements in each line.

Sample Input 0

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

Sample Output 0

-1 -1

Sample Input 1

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

Sample Output 1

0 0

Sample Input 2

5 2 0 0
1 1 0 0 0
1 1 1 0 0
0 1 1 0 0
0 0 1 1 0
0 0 1 1 0
1 1
1 1

Sample Output 2

3 2

Sample Input 3

5 2 2 0
1 1 0 0 0
1 1 1 0 0
0 1 1 0 0
0 0 1 1 3
0 0 1 1 -1
1 1
1 1

Sample Output 3

3 3

Discussion