Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Given a $m\times n$ matrix and a starting position $(i,j)$, how can we find the shortest path to go through all the elements at least once if we can only move by a single unit (i.e. up, right, left or down) at a time?
Currently all I could think of was moving to the nearest corner and then traversing from there, but that would not be the shortest path unless the start position is already a corner. And unfortunately I couldn't find anything similar to this problem.
If either $m=1$ or $n=1$, the starting position will determine how many elements will need to be revisited - head to the nearest end and the back to the other. The following cases consider $m,n>1$.
If either $m$ or $n$ is even, there is a simple traverse starting from any element (and which will conclude on an adjacent element), without revisiting any element.
Consider a $2\times n$ matrix. Then there is a loop traverse that runs one way along one row and back along the other row:
Now for a $2k\times n$ matrix you can stack these loops and jump from loop to loop as required:
(there is no requirement to stagger the loop jumps - that is purely choice). The same idea applies if it is $n$ rather than $m$ that is even.
When $m$ and $n$ are both odd, you do not have a convenient loop path. If for your starting square, $i$ and $j$ are opposite parity - one odd, one even - you cannot avoid one revisit of a cell. A checkerboard colouring argument shows that easily. I believe that otherwise you can complete a path without a revisit, provided you avoiding leaving "dead end" elements until inevitable.
