2179
Encoding moves as offsets
To move to the right or down, we add one to the index of the current column or row. Likewise, to move left or up, we subtract one from the index of the current column or row.
We can encode these moves as two arrays: mvr (short for move row) with the values we should add to the row, and mvc with the values we should add to the column.
// R D L U
int mvr[] = { 0, 1, 0, -1 };
int mvc[] = { 1, 0, -1, 0 };
Since the moves always happen in order (Right, Down, Left, Up), we can encode the direction as an index (dir) into these arrays (which goes from 0 to 3), and changing to the next direction is equivalent to doing (dir + 1) % 4.
Naive ad-hoc
This encoding makes it very easy to ad-hoc the problem, which you can see on walk.c. We simulate every single step by adding offsets to the current row/column, changing direction after every fixed number of steps, and incrementing the number of steps after every two direction changes (Right one, Down one, Left two, Up two, …). When all the cells within the matrix have been visited, we are done.
Without a matrix
Walking the matrix horizontally corresponds to adding or subtracting one to the value of the current cell, while walking vertically corresponds to adding or subtracting N to the value of the current cell.
Knowing this lets us skip the matrix altogether by also encoding the changes to the value of the cell into an array.
// R D L U
int mv[] = { 1, n, -1, -n };
Now we keep track of the value of the current cell by calculating the initial value, then updating it whenever we take a step.
Note that this value is not “correct” while we are walking outside of the matrix (walking up or down would no longer change the value of the cell by N), but since for every step we take away from the matrix we must take another towards the matrix in order to come back, the value will always be correct when we are inside the matrix.
This lets us ad-hoc the problem the exact same way but replacing memory accesses with arithmetic operations, which you can see on nomat.c
Avoiding single steps outside of the matrix
Since we only need to print the value of the current cell while inside the matrix, it is wasteful to walk step by step while outside. The naive adhoc solution can be improved by detecting when we leave the matrix (when the row or column indices go out of bounds) and calculating steps taken outside the matrix all at once, avoiding unnecessary iterations. Some invariants apply, for example we must change direction at least twice to return to the matrix after leaving it, possibly three times when leaving from a corner.
Todo
Avoid unnecessary iterations outside the matrix.