3952: 连环计(挖土机 CSP-J 模拟赛 ~ 第十五场)

内存限制：256 MB 时间限制：2.000 S
评测方式：文本比较 命题人：
提交：2 解决：1

题目描述

33DAI 发现了一片特殊的正方形池塘，池塘可以看作是一个 � 行 � 列的二维数组。每个位置都有特殊的性质。第 � 行第 � 列的特殊性质用正整数 ��,� 描述。

如果 33DAI 往第 � 行第 � 列那个位置丢一个石头，那么就会激发那个位置，溅起很多水花。如果某个位置 (�,�)（第 � 行第 � 列）满足性质 ���(∣�−�∣,∣�−�∣)=��,�，那么水花就会落到那个位置，这会激发那个位置。显然会有多个位置有水花落下从而被激发，所有这些位置会继续激起水花，水花会按照同样规律激发其他位置。

请问往哪个位置丢石头，最终会有最多位置被激发，请输出丢一个石头最多能激发的位置数量。

∣�∣ 表示 � 的绝对值。


输入

一个数 �。

接下来 � 行，每行 � 个整数，第 � 行第 � 列为 ��,�。

输出

输出丢一个石头最多能激发的位置数量。

样例输入 复制 

5
0 1 0 0 0
0 0 2 0 0
0 0 0 0 0
0 6 0 0 1
0 0 0 0 0

样例输出 复制 

18

提示

可以往第一行第二列丢一个石头，这样影响如下（按激发顺序用 A~Z 描述，重复激发只记录第一次激发的字母）： 

B A B 0 C
B B B 0 C
C 0 0 D C
C C C C C
0 0 0 D D

最终被激发了 18 个位置。容易发现，0 的位置和 6 的位置都不会激发其他位置。

数据规模与约定

对于 100% 的数据，1≤�≤100，1≤��,�≤109。

  • 子任务 1（10 分）：保证 ��,�=0。
  • 子任务 2（20 分）：保证 ��,�=�−1。
  • 子任务 3（30 分）：保证 �≤10。
  • 子任务 4（40 分）：没有特殊限制。

来源/分类

提交提交记录统计露一手!