ZUFEOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs ContestProblemSetList
Login Register

问题 CY: 幻方

内存限制：256 MB 时间限制：2 S
题面：传统 评测方式：文本比较 上传者：
提交：117 通过：25
返回比赛提交提交记录

题目描述

        编码员ZS和狒狒克里斯抵达宝库的入口处。入口处有一个n×n的魔法网格，里面填满了整数。克里斯注意到网格中正好有一个单元格是空的，要进入宝库，他们需要在空单元格中填充一个正整数。

克里斯试图填写随机数字，但没有成功。ZS编码员意识到他们需要填写一个正整数，这样网格中的数字就形成了一个神奇的正方形。这意味着他必须填写一个正整数，以便网格的每行、网格的每列和网格的两条长对角线（主对角线和次对角线）中的数字之和相等。

克里斯不知道要填写什么数字。你能帮克里斯找到正确的正整数来填写，或者确定这是不可能的吗？

输入格式

输入的第一行包含一个整数n（2≤n≤500）,即魔法网格的行数和列数。
接下来是n行，每行包含n个整数。第i行中的第j个数字表示ai,j (1≤ai,j≤109 或 ai,j=0)，魔法网格第i行和第j列中的数字。如果相应的单元格为空，ai,j将等于0。否则，ai,j为正。
保证正好有一对整数i，j（1≤i，j≤n），使得ai,j=0。

输出格式

输出一个整数，正整数x（1≤x≤1018），该整数应填充在空单元格中，以便整个网格成为幻方。如果不存在这样的正整数x，则输出-1。


Input 
3
4 0 2
3 5 7
8 1 6
Output 
9
Input 
4
1 1 1 1
1 1 0 1
1 1 1 1
1 1 1 1
Output 
1
Input 
4
1 1 1 1
1 1 0 1
1 1 2 1
1 1 1 1
Output 
-1

输入样例 复制 

3
4 0 2
3 5 7
8 1 6

输出样例 复制 

9

数据范围与提示

在第一个样例中，我们可以在空单元格中填充9，使生成的网格成为一个神奇的正方形。的确，
每行中的数字之和为：
4+9+2=3+5+7=8+1+6=15.
每列中的数字之和为：
4+3+8=9+5+1=2+7+6=15.
两条对角线上的数字之和为：
4+5+6=2+5+8=15.
在第三个样例中，不可能在空正方形中填充一个数字，使生成的网格是一个幻方。

分类标签