1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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:

enter image description here

Now for a $2k\times n$ matrix you can stack these loops and jump from loop to loop as required:

enter image description here

(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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.