魔法护盾
当前没有测试数据。
题目描述
在遥远的魔法大陆上，勇者艾尔接到了一项任务：探访一片神秘的浮空岛屿。浮空岛上分布着一个N × N的格子，每个格子都拥有一个与众不同的魔力等级。为了完成任务，艾尔需要穿越这些格子，并且找到一种方法让他的旅程尽可能顺利。
艾尔每次从当前格子移动到相邻的格子（可以向东、南、西、北四个方向），都会感受到魔力波动的冲击，冲击强度取决于两个格子间的魔力等级差，数值为D。因此，为了在两个格子之间自由穿梭，他必须拥有至少D点魔法护盾(魔法护盾不会被消耗，但是如果冲击超过D就会消失并受到伤害，则旅程失败)。
任务要求艾尔可以从任意位置出发，用最少的护盾强度穿越至少一半的格子（如果格子总数是奇数，那么一半的值向上取整）。
但是，这座浮空岛上魔力波动复杂，路径需要慎重选择。现在，艾尔请求你的帮助，计算出他如果可以从任意位置出发，最少需要多少魔法护盾强度，才能完成这一神秘的探访任务。
你能帮助勇者艾尔成功完成这次冒险吗？
输入格式
第一行为一个整数N。
第2到N+1行每行包含N个非负整数，表示当前格子的魔力等级。
输出格式
输出一个整数，表示需要的护盾强度的最小值。
样例
输入
5
1 1 1 4 4
1 1 1 1 4
1 9 9 4 4
9 9 9 4 4
9 9 9 9 4
输出
3
输入
4
3 2 1 0
2 3 4 5
1 2 3 4
3 4 5 6
输出
1
数据规模
- 测试点1-2：n ≤ 10
- 测试点3-6：n ≤ 100
- 测试点7-10：n ≤ 500
每个格子的魔力等级0 ≤魔力等级 ≤ 10^6。