# Shortest traverse path in a matrix given the start point $(i,j)$

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.