seuOJ467 - 消灭怪物

题目类型：传统
输入文件：标准输入流
输出文件：标准输出流
时间限制：2000 ms
空间限制：256 MiB
题目标签：迎新赛, 2023

题目描述

DingDing 正在玩一个游戏，在游戏中他的任务在击败所有怪物的前提下使得自己在游戏结束时的体力值 $h$ 最大。

在游戏中，DingDing 在一个 $n$ 行 $m$ 列的网格中，网格是四联通的，并且存在着不可以通过的边界，即在不超出边界的情况下，假如 DingDing 当前在点 $(x,y)$ ，那么下一步可以移动到 $(x-1,y),(x+1,y),(x,y-1),(x,y+1)$ 中的任何一个网格中。在一些网格中存在着怪物，每个怪物都有一个体力值 $w$ 。DingDing 初始时位于网格中的第 $x$ 行，第 $y$ 列,且 DingDing 也有自己的初始的体力值 $h$ 。假如DingDing 移动到了相邻的某一个存在怪物的网格，那么：

如果DingDing 当前的体力值 $h$ 严格大于当前的怪物的体力值 $w$ ，那么 DingDing 击败怪物并且获得怪物的体力值 $w$ ，即 $h:=h+w$ 。
否则，DingDing 将击败怪物并且失去当前攻击的怪物的体力值，即 $h:=h-w$ 。（DingDing 的体力值为负数也不会死亡）

当某一个网格中的怪物被击败后，那么这个怪物就会永久死亡，即这个网格点会变成一个没有怪物的点。

请问，假如 DingDing 采取最优的击败怪物的策略，他最终最多能获得多少的体力值呢。

输入格式

第一行，一个整数 $t(1\le t\le 10^4)$ ，代表数据组数。

对于每组数据：
第一行，四个正整数 $n,m,x,y(1\le n,m \le 10^6;1 \le n·m\le 10^6;1\le x \le n; 1\le y\le m)$ ，代表网格的大小与DingDing的初始位置。
接下来的 $n$ 行，每行 $m$ 个正整数 $a_{i,j}(0\le a_{i,j} \le 10^9)$ 。假如 $i=x$ 并且 $j=y$ ，则 $a_{i,j}$ 代表 DingDing 初始的体力值；否则，如果 $a_{i,j}=0$ ，代表此处没有怪物，不然，代表此处有一个体力值为 $w=a_{i,j}$ 的怪物。

保证同一测试点内的 $\sum n·m\le 10^6$ 。

输出格式

对于每组数据，输出一个整数代表DingDing在击败所有怪物的前提下，在游戏结束时的体力值 $h$ 最大值。

样例

输入样例

4
3 3 2 2
1 2 3
4 5 6
7 8 9
2 3 1 1
0 2 0
0 0 3
3 2 1 1
3 1
3 9
7 4
1 3 1 3
1000000000 999999999 1000000000

输出样例

提示
在样例的第 $1$ 组数据中，DingDing 可以按照如下的顺序移动击败怪物 $(2,2)->(2,1)->(1,1)->(1,2)->(1,3)->(2,3)->(3,3)->(2,3)->(2,2)->(3,2)->(3,1)$ 。所有怪物被击败后，DingDing 的体力值为 $45$ ，可以证明的是，在游戏结束时，DingDing 的体力值不可能超过 $45$ 。