P2258 [NOIP 2014 Junior] Submatrix

NOIP 2014 Junior T4.

Definitions: 1. Submatrix: A new matrix formed by selecting some rows and some columns from a matrix and taking the elements at their intersections (preserving the relative order of rows and columns) is called a submatrix of the original matrix. For example, in the table below, selecting rows $2,4$ and columns $2,4,5$ yields a $2 \times 3$ submatrix as follows. |$9$|$\color{#6a5acd}3$|$3$|$\color{#6a5acd}3$|$\color{#6a5acd}9$| |:-|:-|:-|:-|:-| |$\color{#6a5acd}9$|$\color{blue}4$|$\color{#6a5acd}8$|$\color{blue}7$|$\color{blue}4$| |$1$|$\color{#6a5acd}7$|$4$|$\color{#6a5acd}6$|$\color{#6a5acd}6$| |$\color{#6a5acd}6$|$\color{blue}8$|$\color{#6a5acd}5$|$\color{blue}6$|$\color{blue}9$| |$7$|$\color{#6a5acd}4$|$5$|$\color{#6a5acd}6$|$\color{#6a5acd}1$| One of its $2\times3$ submatrices is: |$4$|$7$|$4$| |:-|:-|:-| |$8$|$6$|$9$| 2. Adjacent elements: An element in the matrix is adjacent to its four neighbors above, below, left, and right (if they exist). 3. Score of a matrix: The sum of the absolute differences of every pair of adjacent elements in the matrix. Task: Given a positive-integer matrix with $n$ rows and $m$ columns, choose an $r$-row $c$-column submatrix from it so that the score of this submatrix is minimized, and output that score.

The first line contains four integers $n, m, r, c$ separated by single spaces, as described above. The next $n$ lines each contain $m$ integers, representing the $n$-row $m$-column matrix described in the problem statement.

Output a single integer, the minimum possible score among all submatrices that satisfy the description.

Sample 1 explanation In this matrix, the $2$-row $3$-column submatrix with the minimum score is formed by the intersection of rows $4, 5$ and columns $1, 3, 4$ of the original matrix, namely: |$6$|$5$|$6$| |:-|:-|:-| |$7$|$5$|$6$| Its score is $|6-5|+|5-6|+|7-5|+|5-6|+|6-7|+|5-5|+|6-6|=6$. Sample 2 explanation In this matrix, the $3$-row $3$-column submatrix with the minimum score is formed by the intersection of rows $4, 5, 6$ and columns $2, 6, 7$ of the original matrix. The chosen submatrix with the minimum score is: |$9$|$7$|$8$| |:-|:-|:-| |$9$|$8$|$8$| |$5$|$8$|$10$| Constraints - For $50\%$ of the testdata, $1 \leq n \leq 12$, $1 \leq m \leq 12$, and for every element $1 \leq a_{i,j} \leq 20$. - For $100\%$ of the testdata, $1 \leq n \leq 16$, $1 \leq m \leq 16$, every element satisfies $1 \leq a_{i,j} \leq 1000$, $1 \leq r \leq n$, and $1 \leq c \leq m$. Translated by ChatGPT 5