CODEWITHSUNDEEP
c++mathdistance
SpiceTrader
SpiceTrader

Reputation: 25

Finding target coordinates for Manhattan Distance in 8 Puzzle | C++

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 (x1 , y1) & (x2, y2), the Manhattan Distance = |x1 - x2| + |y1 - y2|

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.

Upvotes: 1

Views: 5547

Answers (2)

E Vakhovsky
E Vakhovsky

Reputation: 44

You probably mean a two dimensional array. Something like you already have in your code int matrix[3][3]

The question you are asking is not very clear as you are not looking for “manhattan distance between two 2D array”, but rather for a “manhattan distance between two specific elements in the array”. For example, a distance between 2 and 6 in your case will be calculated as follows:

Get the two elements’ 2 dimensional coordinates:

Coordinates of 2: x2=1, y2=0 (x and y coordinates of 2)

Coordinates of 6: x6=2, y6=1 (x and y coordinates of 6)

Get the Manhattan distance:

Manhattan distance = abs(x6 – x2) + abs(y6 – y2);

Substitute: abs(2 – 1) + abs(1 – 0);

Answer: 2

Upvotes: 0

therainmaker
therainmaker

Reputation: 4343

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.

Upvotes: 2

Related Questions