1378: 南水北调，东水西送

题目描述

2051年注定是一个不平凡的年份，干旱、洪涝等气象灾害频发，人民的生命与财产安全受到了极大损失。兹年，中国东南部地区普降大雨，以秦岭淮河以南最为明显，蓄水充沛颇有洪泛趋势；西北部地区则遭受了严重的干旱灾害，数月无雨。

2051年的中国已经建成了 $n$ 纵 $n$ 横的网格形互联互通的水库网络，“南水北调，东水西送”的梦想已然成为现实，人民的幸福美好生活终于不再受到涝旱灾害的影响。一方有难，八方支援，党中央第一时间做出决策部署，东南部蓄水最多的水库立刻向西北部蓄水最少的水库输水，保障生产生活的正常运行。

可以认为水库网络是一个 $n \times n$ 的矩阵，用正整数表示蓄水量。按上北下南左西右东分布，即最西北部的水库位于矩阵的左上角，最东南的水库位于矩阵右下角。我们需要找到储水量相对差距最大的两个水库进行输水，储水量少的那个水库必须严格相对在西北，储水量多的那个水库必须严格相对在东南（即两座水库的横、纵坐标均不能相等）。输水结束后，两水库储水量将保持一致。请你输出这一输水过程的输水量。

在党和人民的共同奋斗下，全国上下团结齐心，我们一定能打赢这场输水攻坚战！

输入格式

第一行一个整数 $n$ ，表示代表水库矩阵的长与宽。

接下来的 $n$ 行，每行 $n$ 个正整数代表水库蓄水量。保证每个水库的储水量均为偶数。

输出格式

一个正整数 $x$，代表输水量。

样例输入

样例输入 1

text 3 2 4 6 8 10 12 14 16 18

样例输入 2

text 4 18 10 14 26 8 10 2 22 14 24 24 20 12 2 4 6

样例输出

样例输出 1

text 8

样例输出 2

text 9

数据范围

对于50%的数据，$1\leq n\leq 20$。
对于100%的数据，$1\leq n\leq 2 \times10^3$， $1 \leq 水库蓄水量 \leq 10^6$。保证$x>0$。
取两个数的最小（大）值可以这么写：

c++ int a = 2; int b = 3; int maxx = max(a, b); int minn = min(a, b);

hint：想一想小作业1307数方块是怎么做的？（不允许翻阅OJ上自己曾经提交的代码，违者按作弊处理）

Oops! 本题目还没有解答！

助教老师们编题的速度，已经超过了解题的速度！

OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。

如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！