This question is just for fun; I don't know if it has a nontrivial answer. Let $\Gamma$ be an $n\times n$ square grid, thought of as a graph where the edges of the graph are the edges of the squares of the grid and the vertices of the graph are the vertices of the squares. Vertices of $\Gamma$ have coordinates $(m,k)$, $0\leq m,k \leq n$. Take a subgraph $\Lambda$ of $\Gamma$. So it looks like this:

alt text http://www.ich-liebt-du.de/wp-content/uploads/2008/09/labyrinth.jpg

Let $\Delta$ be the "frame", i.e. the subgraph of $\Gamma$ of points with at least one coordinate equal to $n$, and all the edges between them. Let $A=(x,0)$ , $0 < x < n$, be a point on the lower edge (the entrance) and likewise $\Omega =(y,n)$, $0 < y < n$, a point in the upper edge (the exit).

We say that $\Lambda$ is an $n\times n$ $(A,\Omega)$-*labyrinth* if it is connected and $A,\Omega\in\Lambda$.

Theseus enters the labyrinth at $A$ and has to reach $\Omega$. He only knows what I said above (except he does *not* know the value of $n$) and of course ignores the structure of $\Lambda$ and the position of $A$ and $\Omega$ in the lower (respectively upper) edge. At each point (vertex) $v$, just by looking, he has only the following information:

- Whether $v$ is equal to $A$, or to $\Omega$.
- How long are the maximal forward, backward, left and right straight paths $S$ starting from $v$ contained in $\Lambda$. Some lengths may be $0$.
- Whether or not the "end" of $S$ different from $v$ lies in $\Delta$.
- Whether or not the "end" of $S$ different from $v$ is $\Omega$, and whether it's $A$.

Since he enters at $A$, Theseus has a strategy. A *strategy* is a function that, at each vertex, tells him whether to go forward (resp. bacwards, left or right) by one step depending on the path that has already been walked and on the information gathered so far.

Let $D(\Lambda)$ be the smallest number of steps he must do in order to get to $\Omega$, where the minimum is taken over all the possible strategies.

The question is:

Given $n$, $A$ and $\Omega$, how to construct a labyrinth $\Lambda$ that maximizes $D(\Lambda)$ ?

I'm interested in aswers, if there can be, that do **not** involve listing all possible strategies and all possible graphs with a "computer".