55036 - [NOIP2014] 子矩阵

给出如下定义:

  1. 子矩阵:从一个矩阵当中选取某些行和某些列交叉位置所组成的新矩阵(保持行与列的相对顺序)被称为原矩阵的一个子矩阵。

    例如,下面图中选取第 2,4 行和第 2,4,5 列交叉位置的元素得到一个 2 \times 3 的子矩阵如下所示。

9\color{#6a5acd}33\color{#6a5acd}3\color{#6a5acd}9
\color{#6a5acd}9\color{blue}4\color{#6a5acd}8\color{blue}7\color{blue}4
1\color{#6a5acd}74\color{#6a5acd}6\color{#6a5acd}6
\color{#6a5acd}6\color{blue}8\color{#6a5acd}5\color{blue}6\color{blue}9
7\color{#6a5acd}45\color{#6a5acd}6\color{#6a5acd}1

此矩阵的其中一个 2\times3 的子矩阵是:

474
869
  1. 相邻的元素:矩阵中的某个元素与其上下左右四个元素(如果存在的话)是相邻的。

  2. 矩阵的分值:矩阵中每一对相邻元素之差的绝对值之和。

本题任务:给定一个 nm 列的正整数矩阵,请你从这个矩阵中选出一个 rc 列的子矩阵,使得这个子矩阵的分值最小,并输出这个分值。

输入

第一行包含用空格隔开的四个整数 n,m,r,c,意义如问题描述中所述,每两个整数之间用一个空格隔开。

接下来的 n 行,每行包含 m 个用空格隔开的整数,用来表示问题描述中那个 nm 列的矩阵。

输出

一个整数,表示满足题目描述的子矩阵的最小分值。

样例

输入

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

输出

6

输入

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

输出

16

提示

样例 1 说明

该矩阵中分值最小的 23 列的子矩阵由原矩阵的第 4 行、第 5 行与第 1 列、第 3 列、第 4 列交叉位置的元素组成,为:

656
756

其分值为 |6-5|+|5-6|+|7-5|+|5-6|+|6-7|+|5-5|+|6-6|=6

样例 2 说明

该矩阵中分值最小的 33 列的子矩阵由原矩阵的第 4 行、第 5 行、第 6 行与第 2 列、第 6 列、第 7 列交叉位置的元素组成,选取的分值最小的子矩阵为:

978
988
5810

数据范围

  • 对于 50\% 的数据,1\leq n\leq 121\leq m\leq 12,矩阵中的每个元素 1\leq a_{i,j}\leq20

  • 对于 100\% 的数据,1\leq n\leq 161\leq m\leq 16,矩阵中的每个元素 1\leq a_{i,j}\leq 10001\leq r\leq n1\leq c\leq m

来源

NOIP2014 普及组 T4

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题