Maximum Neighborhood

The main trap is assuming the biggest number, $n^2$, must give the biggest cost. Nope. The bottom-right corner has the largest cell value, but it only has two neighbors. Sometimes a slightly smaller cell with more neighbors wins. Borders matter. Annoying, but easy.

Cell Values

Use 1-indexed coordinates. The value at row $i$, column $j$ is:

$(i-1)n+j$

So we do not need to build the whole grid. We can compute any cell's value instantly.

Cost Of One Cell

A cell's cost is:

• its own value,
• plus the value above it, if it exists,
• plus the value below it, if it exists,
• plus the value to the left, if it exists,
• plus the value to the right, if it exists.

That is it. No diagonal nonsense.

For example, if $n=4$ and we choose the cell with value $15$, it has neighbors $11$, $14$, and $16$, so the cost is:

$15+11+14+16=56$

Why Brute Force Is Completely Fine

The constraints are tiny:

$n \le 100$

There are at most $100^2=10000$ cells per test case, and at most $100$ test cases. For each cell, we check only $4$ directions.

So the total work is around:

$100 \cdot 10000 \cdot 4 = 4{,}000{,}000$

That is baby food for C++. No need to summon some overengineered formula dragon.

Algorithm

For each test case:

1. Read $n$.
2. Initialize answer = 0.
3. For every row i from $1$ to $n$:
4. For every column j from $1$ to $n$:
5. Start cost as the value of $(i,j)$.
6. Try the four neighboring directions.
7. If the neighbor is inside the grid, add its value.
8. Update answer.
9. Print answer.

Correctness Proof

We need to prove the algorithm prints the maximum possible cell cost.

For any cell $(i,j)$, the algorithm computes its own value using the formula $(i-1)n+j$. Then it checks exactly the four side-adjacent positions: up, down, left, and right. If such a position is inside the grid, the algorithm adds that neighbor's value to the current cost. Therefore, for every cell, the algorithm computes exactly the cost defined in the statement.

The algorithm iterates over every cell in the $n \times n$ grid. Since every possible candidate cell is considered, and since the computed cost for each candidate is exact, taking the maximum over all computed costs gives exactly the maximum cost among all cells.

Therefore, the algorithm is correct.

Complexity

There are $n^2$ cells, and for each cell we check $4$ neighbors.

Time complexity:

$O(n^2)$

Memory complexity:

$O(1)$