What is the length of the longest possible shortest path on an n × n grid? Let $M \in \{0, 1\}^{n \times n}$ be a grid. 0 represents a free field, 1 a blocked field. You can move in four directions: up, down, left, right.
Given the worst possible start and end position on the worst possible $n \times n$ grid, what is the length of the shortest path?
 A: While writing this question, I created a couple of examples and I'm pretty sure I found at least a part of the answer.
uneven $n$
The worst possible grid uses a zig-zag pattern. The start is at lower left and the end at the right. Every second line has $n-1$ blocking elements. There are $\frac{n-1}{2}$ of such lines, leading to $(n-1) \cdot \frac{n-1}{2} = \frac{n^2 -2n + 1}{2}$ blocking elements. We are already at a start position. This means the longest path is the number of remaining elements minus 1:
\begin{align}
    f(n) &= n^2 - \frac{n^2 -2n + 1}{2} - 1\\
&= \frac{n^2}{2} + n - \frac{3}{2}
\end{align}
Some examples:


*

*$f(1) = 0$

*$f(3) = 4 + 3 - 1 = 6$

*$f(5) = 11 + 5 = 16$
Simple examples


*

*$n=1$: 0 steps - start and end have to be equal

*$n=3$: 6 steps - see example


Example grid:
o o o
o x o
s x t



*

*$n = 5$: 


Example grid:
o o o x e
o x o x o
o x o x o
o x o x o
s x o o o

Even $n$
For even $n$, using the same pattern, one can achieve at least $f(n-1) + (n-1)$. I'm not convinced that this is the maximum, though.
This would give:


*

*$f(2) = 1$ (found better solution)

*$f(4) = 8$ (found better solution)

*$f(6) = 21$
Examples


*

*$n = 2$: 2 steps - start and end are opposing diagonal points

*$n = 4$: 10 steps - see example


Example grid:
o o o o
o x x o
o x o o
s x e o

Example $6 \times 6$ grid: 21 steps
o o o x e o
o x o x o o
o x o x o o
o x o x o o
o x o x x o
s x o o o o

