Background

This is an interactive problem. You only need to implement the function required in the code.

Your code does not need to include any additional header files, and you do not need to implement the main function.

This problem only supports C++ submissions.

Problem Description

In the city of Debrecen, there is a square forest called Nagyerdő, which can be viewed as an $N \times N$ grid. The rows of the grid are numbered from $0$ to $N - 1$ from north to south, and the columns are numbered from $0$ to $N - 1$ from west to east. The cell in row $r$ and column $c$ is called cell $(r, c)$.

Each cell in the forest is either empty or has a tree. There is at least one empty cell in the forest.

DVSC is the most famous sports club in the city and is currently planning to build a new football stadium in the forest. A stadium of size $s$ (where $s \ge 1$) is a set of $s$ distinct empty cells $(r_0, c_0), \ldots, (r_{s - 1}, c_{s - 1})$. Formally, this means:

• For each $i$ from $0$ to $s - 1$ (inclusive), the cell $(r_i, c_i)$ is empty;
• For each pair $i$ and $j$ such that $0 \le i \lt j \lt s$, at least one of $r_i \neq r_j$ and $c_i \neq c_j$ holds.

When playing, the ball is passed between the cells of the stadium. A direct pass is one of the following two actions:

• The stadium contains all cells between $(r,a)$ and $(r,b)$ in row $r$, and the ball is passed from cell $(r,a)$ to cell $(r,b)$ ($0 \le r,a,b \lt N, a \ne b$). The containment is defined formally as:
  • If $a \lt b$, then the stadium should contain every cell $(r,k)$ such that $a \le k \le b$;
  • If $a \gt b$, then the stadium should contain every cell $(r,k)$ such that $b \le k \le a$.
• The stadium contains all cells between $(a,c)$ and $(b,c)$ in column $c$, and the ball is passed from cell $(a,c)$ to cell $(b,c)$ ($0 \le c,a,b \lt N, a \ne b$). The containment is defined formally as:
  • If $a \lt b$, then the stadium should contain every cell $(k, c)$ such that $a \le k \le b$;
  • If $a \gt b$, then the stadium should contain every cell $(k, c)$ such that $b \le k \le a$.

A stadium is called regular if it is possible to pass the ball from any cell of the stadium to any other cell of the stadium using at most $2$ direct passes. Note that any stadium of size $1$ is regular.

For example, consider a forest of size $N = 5$ in which cells $(1,0)$ and $(4,2)$ have trees and all other cells are empty. The figure below shows three possible stadiums. Cells with trees are shown in dark color, and cells belonging to the stadium are hatched.

The stadium on the left is regular. However, the stadium in the middle is not regular, because passing the ball from cell $(4,1)$ to cell $(4,3)$ requires at least $3$ direct passes. The stadium on the right is also not regular, because it is impossible to pass the ball from cell $(3,0)$ to cell $(1,3)$ using direct passes.

The club wants to build the largest possible regular stadium. Your task is to find the maximum value of $s$ such that a regular stadium of size $s$ can be built in the forest.

Input Format

You need to implement the following function:

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

• $N$: the size of the forest.
• $F$: an array of length $N$, where each element is an array of length $N$, describing the cells of the forest. For each $r$ and $c$ such that $0 \le r \lt N$ and $0 \le c \lt N$, $F[r][c] = 0$ means cell $(r, c)$ is empty, and $F[r][c] = 1$ means the cell has a tree.
• The function should return the maximum size of a regular stadium that can be built in the forest.
• For each test case, this function is called exactly once.

Output Format

Consider the following call:

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]])

The forest described by this example is shown on the left of the figure below, and a regular stadium of size $20$ is shown on the right:

Since there is no regular stadium of size $21$ or larger, the function should return $20$.

Hint

Constraints

• $1 \le N \le 2\,000$
• $0 \le F[i][j] \le 1$ (for all $i$ and $j$ such that $0 \le i \lt N$ and $0 \le j \lt N$)
• There is at least one empty cell in the forest. That is, there exist $i$ and $j$ such that $0 \le i \lt N$ and $0 \le j \lt N$ and $F[i][j] = 0$.

Subtasks

1. (6 points) At most one cell has a tree.
2. (8 points) $N \le 3$.
3. (22 points) $N \le 7$.
4. (18 points) $N \le 30$.
5. (16 points) $N \le 500$.
6. (30 points) No additional constraints.

In each subtask, if your program can correctly determine whether the set of all empty cells can form a regular stadium, then you will receive 25% of the partial score for that subtask.

More precisely, for test cases where the set of all empty cells is a regular stadium, your solution is scored as follows:

• If you return the correct answer (that is, the number of all empty cells), you get full score;
• Otherwise, you get 0 points.

For test cases where the set of all empty cells is not a regular stadium, your solution is scored as follows:

• If you return the correct answer, you get full score;
• If you return the number of all empty cells, you get 0 points;
• If you return any other value, you get 25% of the score.

The score for each subtask is the minimum score among all test cases in that subtask.

Sample grader

The sample grader reads the input in the following format:

• Line $1$: $N$.
• Line $2 + i$ ($0 \le i \lt N$): $F[i][0] \; F[i][1] \; \ldots \; F[i][N - 1]$.

The sample grader prints your answer in the following format:

• Line $1$: the return value of the function biggest_stadium.

Translated by ChatGPT 5