Consider a grid, $N x N$ in size, with cells colored white or black. It can be encoded naturally by a word from $\{0,1\}^{n^2}$. Show that a deterministic Turing machine with logarithimic memory can decide if there exists a monochromatic path from the top row to the borrom row.
Allowed moves: up, down, left, right. No diagonal moves.
This isn't homework, but a question from a quiz I've taken today.
Paths can be very long, even $O(n^2)$ in size, so performing a DFS/BFS simulation is not possible. Methods like "right hand rule" for solving mazes seem not applicable.
You can prove this by simply reducing your problem to general st-connectivity for undirected graphs. Every cell is a node, connected to its neighbours iff it has the same color. Additionally you add 2 nodes. one that connects to every cell in the top row, one that connects to every cell in the bottom row. That problem then is solvable in $L$, as Omer Reingold proved in 2004.
That of course is a rather lazy (never the less correct) way to prove it. If you have to provide an algorithm, you can either refer to the original paper ( http://eccc.hpi-web.de/eccc-reports/2004/TR04-094/ ) or you can look if you find a simpler one. Maybe the algorithm for USTCON on grid graphs is a bit easier.