当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

6506:Problem G. Spin A Web

题目描述
We have a canvas divided into grid with H rows and W columns. The square at the $i_th$ row from the top and the $j_th$ column from the left is represented as (i, j). (i, j) square has two value xi,j and yi,j .
Now we want to merge the squares to a connected web with minimal cost. Two squares can be connected if they are in the same row or column, and the cost of connecting ($i_0$, $j_0$) and ($i_1$, $j_1$) is|$x_{i_0,j_0}$ - $x_{i_1,j_1}$| + |$y_{i_0,j_0}$ - $y_{i_1,j_1}$|
输入解释
Input is given from Standard Input in the following format:
H W
$x_{1,1}$ $x_{1,2}$ ... $x_{1,W}$
...
...
...
$x_{H,1}$ $x_{H,2}$ ... $x_{H,W}$
$y_{1,1}$ $y_{1,2}$ ... $y_{1,W}$
...
...
...
$y_{H,1}$ $y_{H,2}$ ... $y_{H,W}$
Constraints
1 ≤ H × W ≤ 100000
− 108 ≤ $x_{i,j}$ , $y_{i,j}$ ≤ 10^8(1 ≤ i ≤ H, 1 ≤ j ≤ W)
All of them are integers.
输出解释
Print one line denotes the minimal cost to merge the square to be a connected web
输入样例
1 3
1 3 2
1 2 3
2 2
1 4
2 3
2 1
3 4
输出样例
5
8
来自杭电HDUOJ的附加信息
Recommend

该题目是Virtual Judge题目,来自 杭电HDUOJ

源链接: HDU-6506

最后修改于 2020-10-25T23:31:56+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
15000/10000MS(Java/Others) 262144/262144K(Java/Others)