Problem Background

NOIP2014 Junior Group T4

Problem Description

The following definitions are given:

1. Submatrix: A submatrix of a matrix is a new matrix formed by selecting certain rows and certain columns from the original matrix and taking the elements at their intersections (maintaining the relative order of rows and columns).

   For example, selecting the $2,4$ rows and the $2,4,5$ columns from the matrix below results in a $2 \times 3$ submatrix as shown:

One of the $2 \times 3$ submatrices is:

1. Adjacent Elements: Elements in a matrix that are directly above, below, left, or right of a given element (if they exist) are considered adjacent.

2. Matrix Score: The sum of the absolute differences between each pair of adjacent elements in the matrix.

Task: Given an $n$ by $m$ matrix of positive integers, select an $r$ by $c$ submatrix such that the score of this submatrix is minimized, and output this score.

Input Format

The first line contains four integers $n, m, r, c$ separated by spaces, as described in the problem.

The next $n$ lines each contain $m$ integers separated by spaces, representing the $n$ by $m$ matrix.

Output Format

A single integer representing the minimum score of the submatrix as described in the problem.

Sample Input and Output

Input Sample #1

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

Output Sample #1

6

Input Sample #2

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

Output Sample #2

16

Notes

Sample 1 Explanation

The submatrix with the minimum score of $2$ rows and $3$ columns is formed by the $4$th and $5$th rows and the $1$st, $3$rd, and $4$th columns of the original matrix:

The score is calculated as $|6-5| + |5-6| + |7-5| + |5-6| + |6-7| + |5-5| + |6-6| = 6$.

Sample 2 Explanation

The submatrix with the minimum score of $3$ rows and $3$ columns is formed by the $4$th, $5$th, and $6$th rows and the $2$nd, $6$th, and $7$th columns of the original matrix:

Data Range

• For $50\%$ of the data, $1 \leq n \leq 12$, $1 \leq m \leq 12$, and each element in the matrix $1 \leq a_{i,j} \leq 20$.
• For $100\%$ of the data, $1 \leq n \leq 16$, $1 \leq m \leq 16$, each element in the matrix $1 \leq a_{i,j} \leq 1000$, and $1 \leq r \leq n$, $1 \leq c \leq m$.

见题面 Input 部分

见题面 Output 部分