题目描述

Debrecen 市的 Nagyerdő 森林是一片 $N \times N$ 的方格，方格的行由北向南从 $0$ 到 $N-1$ 编号，列由西向东从 $0$ 到 $N-1$ 编号。第 $r$ 行第 $c$ 列的格子称为单元格 $(r, c)$。

森林的每个单元格要么是空的（可用于建造），要么是有树的（不可用），且至少有一个空单元格。

DVSC 俱乐部计划修建足球场，球场的定义与规则如下：

1. 球场的定义

大小为 $s$（$s \ge 1$）的球场，是 $s$ 个互不相同的空单元格集合 $\{(r_0, c_0), (r_1, c_1), \ldots, (r_{s-1}, c_{s-1})\}$，需满足：

• 对所有 $0 \le i \lt s$，单元格 $(r_i, c_i)$ 是空的（$F[r_i][c_i] = 0$）；
• 对所有 $0 \le i \lt j \lt s$，$r_i \neq r_j$ 和 $c_i \neq c_j$ 中至少有一个成立（即任意两个单元格不同时在同一行且同一列）。

2. 直传的定义

直传是以下两种动作之一：

• 行直传：若球场包含第 $r$ 行中单元格 $(r,a)$ 和 $(r,b)$ 之间的全部单元格，则球可从 $(r,a)$ 传递到 $(r,b)$（$a \neq b$）。具体包含关系为：
  • 若 $a < b$，则球场需包含所有满足 $a \le k \le b$ 的单元格 $(r, k)$；
  • 若 $a > b$，则球场需包含所有满足 $b \le k \le a$ 的单元格 $(r, k)$。
• 列直传：若球场包含第 $c$ 列中单元格 $(a,c)$ 和 $(b,c)$ 之间的全部单元格，则球可从 $(a,c)$ 传递到 $(b,c)$（$a \neq b$）。具体包含关系为：
  • 若 $a < b$，则球场需包含所有满足 $a \le k \le b$ 的单元格 $(k, c)$；
  • 若 $a > b$，则球场需包含所有满足 $b \le k \le a$ 的单元格 $(k, c)$。

3. 规则球场的定义

若通过至多 2 次直传，可将球从球场的任意单元格传递到另一任意单元格，则该球场是“规则的”。注意，大小为 $1$ 的球场必然是规则的。 

你的任务是找出森林中可建造的最大规则球场的大小 $s$。

实现细节

需在程序开始引入库 soccer.h，并实现以下函数：

int biggest_stadium(int N, int[][] F)

参数说明

• $N$：森林的大小（即方格为 $N \times N$）；
• $F$：描述森林的二维数组，$F[r][c] = 0$ 表示单元格 $(r,c)$ 为空，$F[r][c] = 1$ 表示有树。

返回要求

返回可建造的最大规则球场的大小 $s$。每个测试用例中，该函数仅被调用一次。

例子

考虑以下函数调用：

biggest_stadium(5, [[0, 0, 0, 0, 0],  
                    [1, 0, 0, 0, 0], 
                    [0, 0, 0, 0, 0], 
                    [0, 0, 0, 0, 0], 
                    [0, 0, 1, 0, 0]])

该例子中，森林里仅有 $(1,0)$ 和 $(4,2)$ 两个单元格有树，其余均为空。可建造的最大规则球场大小为 $20$（总空单元格数为 $23$，但部分空单元格无法组成更大的规则球场），因此函数返回 $20$。 

约束条件

• $1 \le N \le 2000$；
• 对所有 $0 \le i \lt N$、$0 \le j \lt N$，$F[i][j] \in \{0, 1\}$；
• 森林中至少有一个空单元格（即存在 $i,j$ 使得 $F[i][j] = 0$）。

子任务

子任务	附加限制	分值
1	至多只有一个单元格有树	$6$
2	$N \le 3$	$8$
3	$N \le 7$	$22$
4	$N \le 30$	$18$
5	$N \le 500$	$16$
6	无额外约束	$30$

子任务部分分规则

对于每个子任务，若程序能正确判定“全部空单元格组成的集合是否为规则球场”，可获得该子任务 $25\%$ 的部分分，具体规则如下：

1. 若全部空单元格组成规则球场：
   • 程序返回空单元格总数（正确答案）→ 得该测试用例满分；
   • 程序返回其他值 → 得 $0$ 分。
2. 若全部空单元格不组成规则球场：
   • 程序返回正确答案 → 得该测试用例满分；
   • 程序返回空单元格总数 → 得 $0$ 分；
   • 程序返回其他值 → 得该测试用例 $25\%$ 的分数。

每个子任务的最终得分，取该子任务所有测试用例得分的最小值。

评测程序示例

输入格式

1. 第 $1$ 行：整数 $N$；
2. 第 $2+i$ 行（$0 \le i \lt N$）：$N$ 个整数，依次表示 $F[i][0], F[i][1], \ldots, F[i][N-1]$。

输出格式

第 $1$ 行：函数 biggest_stadium 的返回值。