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.