Nik - 1 year ago 78

Java Question

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.

Answer

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 (x_{i}, y_{i}), 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
```

Source (Stackoverflow)