How to calculate distance between 2 points in a 2D matrix

Question

I am both new to this website and new to C. I need a program to find the average 'jumps' it takes from all points.

The idea is this: Find "jump" distance from 1 to 2, 1 to 3, 1 to 4 ... 1 to 9, or find 2 to 1, 2 to 3, 2 to 4 2 to 5 etc.

Doing them on the first row is simple, just (2-1) or (3-1) and you get the correct number. But if I want to find the distance between 1 and 4 or 1 to 8 then I have absolutely no idea. The dimensions of the matrix should potentially be changeable. But I just want help with a 3x3 matrix.

Anyone could show me how to find it?

Jump means vertical or horizontal move from one point to another. from 1 to 2 = 1, from 1 to 9 = 4 (shortest path only)

Solution 1

What is the definition of "jump-distance" ?

If you mean how many jumps a man needs to go from square M to N, if he can only jumps vertically and horizontally, one possibility can:

dist = abs(x2 - x1) + abs(y2 - y1);

For example jump-distance between 1 and 9 is: |3-1|+|3-1| = 4

Solution 2

The definition of "distance" on this kind of problems is always tricky.

Imagine that the points are marks on a field, and you can freely walk all over it. Then, you could take any path from one point to the other. The shortest route then would be a straight line; its length would be the length of the vector that joins the points, which happens to be the difference vector among two points' positions. This length can be computed with the help of Pythagora's theorem: dist = sqrt((x2-x1)^2 + (y2-y1)^2). This is known as the Euclidian distance between the points.

Now imagine that you are in a city, and each point is a building. You can't walk over a building, so the only options are to go either up/down or left/right. Then, the shortest distance is given by the sum of the components of the difference vector; which is the mathematical way of saying that "go down 2 blocks and then one block to the left" means walking 3 blocks' distance: dist = abs(x2-x1) + abs(y2-y1). This is known as the Manhattan distance between the points.

In your problem, however, it looks like the only possible move is to jump to an adjacent point, in a single step, diagonals allowed. Then the problem gets a bit trickier, because the path is very irregular. You need some Graph Theory here, very useful when modeling problems with linked elements, or "nodes". Each point would be a node, connected to their neighbors, and the problem would be to find the shortest path to another given point. If jumps had different weights (for instance, is jumping in diagonal was harder), an easy way to solve this is would be with the Dijkstra's Algorithm; more details on implementation at Wikipedia.

If the cost is always the same, then the problem is reduced to counting the number of jumps in a Breadth-First Search of the destination point from the source.

Solution 3

Let's define the 'jump' distance : "the number of hops required to reach from Point A [A_x,A_y] to Point B [B_x,B_y]."

Now there can be two ways in which the hops are allowed :

1. Horizontally/Vertically
   In this case, you can go up/down or left/right. As you have to travel X axis and Y axis independently, your ans is:
   jumpDistance = abs(Bx - Ax) + abs(By - Ay);

2. Horizontally/Vertically and also Diagonally
   In this case, you can go up/down or left/right and diagonally as well. How it differs from Case 1 is that now you have the ability to change your X axis and Y axis together at the cost of only one jump . Your answer now is:
   jumpDistance = Max(abs(Bx - Ax),abs(By - Ay));