A7549. [ABC147E] Balanced Path
编程题
普及/提高-
知识点
题目描述
有一个高为 $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)$），定义**偏差**为「路径上格子红色数字之和」与「路径上格子蓝色数字之和」的差的绝对值。
高桥君希望通过恰当选择涂色方案和移动路径，使偏差尽可能小。
请求出偏差的最小值。
格子 $(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}$
> $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$。
- $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$。
