Given is a grid of size N imes N. It contains numbers from 1 to N^2. You start at the cell numbered 1, move to 2, then to 3, and so on up till N^2. Report the total manhattan distance traversed in doing so.
Subtask 1 and 2
We keep an array M of size N^2 and a variable Dist = 0. M* stores the coordinates of number i in the grid. Let M*.x denote the x-coordinate and M*.y denote the y-coordinate. Dist stores the total distance moved. Once array M has been filled, we can iterate from i\,=\,1 to N^2 and keep increasing the variable Dist by the distance moved while going from i-1 to i:
Dist = Dist + abs(\,M*.x-M[i-1].x)\,\, + abs(\,M*.y-M[i-1].y)\,\,
Note that Manhattan distance between i and i-1 is being added to Dist. This is because the question says that you can only move from one cell to another if the latter shares an edge with the former.