CODEWITHSUNDEEP
cmatrixdistance
Val
Val

Reputation: 23

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

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.

enter image description here

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)

Upvotes: 2

Views: 22071

Answers (4)

Shivam Singh
Shivam Singh

Reputation: 366

There are two ways to calculate jump distance. 1) when only horizontal and vertical movements are allowed, in that case all you need to do is form a rectangle in between the two points and calculate the length of two adjacent side. Like if you want to move from 1 to 9 then first move from 1 to 3 and then move from 3 to 9. (Convert it to code) 2) when movements in all eight directions are allowed, things get tricky. Like if you want to move from 1 to 6 suppose. What you'll need to do is you'll have to more from 1 to 5. And then from 5 to 6. The way of doing it in code is to find the maximum in between the difference in x and y coordinates. In this example, in x coordinate, difference is 2 (3-1) and in y coordinate, difference is 1 (2-1). So the maximum of this is 2. So here's the answer. (Convert to code)

Upvotes: 0

GiriB
GiriB

Reputation: 1313

Let's define the 'jump' distance : "the number of hops required to reach from Point A [Ax,Ay] to Point B [Bx,By]."

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));

Upvotes: 8

lemonzi
lemonzi

Reputation: 461

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.

Upvotes: 7

masoud
masoud

Reputation: 56549

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

Upvotes: 2

Related Questions