← 返回题目
题库练习 [ABC147E] Balanced Path
← 上一题 下一题 →

A7549 | [ABC147E] Balanced Path

时间限制1s
内存限制256MB
通过 / 提交0/0

题目描述

有一个高为 $H$ 格、宽为 $W$ 格的网格。从上往下第 $i$ 行、从左往右第 $j$ 列的格子称为格子 $(i,j)$。

格子 $(i,j)$ 上写有两个数字 $A_{ij}$ 和 $B_{ij}$。

高桥君首先需要对每个格子，将这两个数字中的一个涂成红色，另一个涂成蓝色。

之后，他从格子 $(1,1)$ 移动到格子 $(H,W)$。高桥君每次行动可以从格子 $(i,j)$ 移动到格子 $(i+1,j)$ 或格子 $(i,j+1)$，不能超出网格范围。

对于这条移动路径（包含格子 $(1,1)$ 和格子 $(H,W)$），定义**偏差**为「路径上格子红色数字之和」与「路径上格子蓝色数字之和」的差的绝对值。

高桥君希望通过恰当选择涂色方案和移动路径，使偏差尽可能小。

请求出偏差的最小值。

输入格式

输入按以下格式从标准输入给出：

> $H$ $W$
> $A_{11}$ $A_{12}$ $\ldots$ $A_{1W}$
> $\vdots$
> $A_{H1}$ $A_{H2}$ $\ldots$ $A_{HW}$
> $B_{11}$ $B_{12}$ $\ldots$ $B_{1W}$
> $\vdots$
> $B_{H1}$ $B_{H2}$ $\ldots$ $B_{HW}$

输出格式

请输出偏差的最小值。

输入输出样例

输入 #1
2 2
1 2
3 4
3 4
2 1
输出 #1
0
输入 #2
2 3
1 10 80
80 10 1
1 2 3
4 5 6
输出 #2
2
C++ 编辑器
输入
输出