SpiceTrader - 8 months ago 83

C++ Question

I'm trying to find a way to calculate the manhattan distance between two 2D array's containing numbers between 0 and 8. Assuming one of the arrays (the goal for the 8 puzzle) is:

`1 2 3`

4 5 6

7 8 0

I understand that between (x

Manhattan Distance = |x

My code looks something like:

`for(x = 0; x < 3; x++){`

for(y = 0; y < 3; y++){

int value = matrix[x][y];

int targX; //Target X coordinate

int targY; //Target Y coordinate

int distX = abs(x - targX);

int distY = abs(y - targY);

mDist = mDist + distX + distY;

}

}

I'm having trouble finding a way to get the target coordinates for any particular value.

Answer

Target coordinates for a value `n`

are `((n-1) div 3, (n-1) mod 3)`

The above values will be defined assuming the origin `(0,0)`

to be at the top left corner, i.e. the square where 1 will be placed. X coordinates increase in the right direction, and Y coordinates in the downward direction.

Source (Stackoverflow)