1

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?

Martin Thoma
  • 9,821

1 Answers1

2

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
Martin Thoma
  • 9,821