Nik - 1 year ago 123
Java Question

# Quick algorithm for distance between 2 points on a grid?

Given a grid of width by length (say 5 x 4) and an array of X and Y coords for points on that grid, print the distance from each point on the grid to the coords as below:

width = 5

len = 4

x coords = (2,3)

y coords = (2,4)

``````2123
1012
2112
2101
3212
``````

A move "across" is + 2, vertical or horizontal move is +1

Assume xCoords.length = yCoords.length

I will post my solution later, or rather an attempt at a solution. I got stuck trying to come up with a function to transpose distance from grid coordinates (i,j) to coordinates for the points... So basically

``````for i .. width
for j .. length
getDistance(i,j, xCoords,yCoords)
``````

(0,0) (0,1) (0,2) (0,3)

(1,0) (1,1) (1,2) (1,3)

(2,0) (2,1) (2,2) (2,3)

etc...

To the actual distance values at those coordinates.

I assume that you are looking for the distance to the nearest `coord` among the ones given in the vector, i.e.

``````for i 0 .. width
for j 0 .. length
best = distance(i, j, coords[0].x, coords[0].y)
for k 1 .. coordVector // Skip first element
best = min(best, distance(i, j, coords[k].x, coords[k].y)
result[i][j] = best
``````

The third nested loop checks the distance from the given coordinate to all coordinates in the vector of (xi, yi), picks the shortest one, and stores it in the variable `best`. Note that `best` is initialized with the distance to the first point in the vector, so the nested loop starts with the second point.

All you need now is a calculator for `distance`. According to the problem description, you are looking for Manhattan Distance because a diagonal step is weighted as 2, meaning it's the same as one step horizontally plus one step vertically:

``````distance(x0, y0, x1, y1)
horizontal = abs(x1-x0)
vertical = abs(y0-y1)
return horizontal + vertical
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download