AT_abc147_e [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) $），定义**偏差**为「路径上格子红色数字之和」与「路径上格子蓝色数字之和」的差的绝对值。
高桥君希望通过恰当选择涂色方案和移动路径，使偏差尽可能小。
请求出偏差的最小值。
输入格式
输入按以下格式从标准输入给出：
> $ 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} $
输出格式
请输出偏差的最小值。
说明/提示
### 约束条件
- $ 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 $。
---