AT_abc147_e.[ABC147E] Balanced Path

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有一个高为 $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
```

说明/提示

约束条件

$2 \leq H \leq 80$
$2 \leq W \leq 80$
$0 \leq A_{ij} \leq 80$
$0 \leq B_{ij} \leq 80$
输入中的所有值均为整数。

样例解释 1

按照下图的涂色方案和移动路径选择，路径上的红色数字之和为 $3+3+1=7$ ，蓝色数字之和为 $1+2+4=7$ ，可以将偏差控制为 $0$ 。

首页