CODEWITHSUNDEEP
algorithmgridpoints
peeyush
peeyush

Reputation: 2931

finding distance between 2 points in grid when move is restricted

There are various points in a Grid.

Say (x,y) can be reached from (x-1,y+1) in a single unit of time. then what would be the general formula for finding distance between a point (x1,y1) to (x2,y2).

say for (0,0) to (-2,-1) i.e. coordinate can be negative too.

I could not think of general formula.

Upvotes: 1

Views: 1500

Answers (2)

Stefan Haustein
Stefan Haustein

Reputation: 18803

If I understand the question correctly, and diagonal movements have the same cost as "manhattan" movements, it's cheaper than the manhattan distance in most cases -- only the maximum of the x and y distances is relevant:

max(abs(x1 - x2), abs(y1 - y2))

Basically you move diagonally at cost 1 per unit until you have reached x2 or y2, then along the grid.

Upvotes: 3

sukunrt
sukunrt

Reputation: 1543

if (x,y) can be reached from (x-1, y+1). Then all points reachable from (x1,y1) are (x1+k, y1-k) where k is greater than 0.

Upvotes: -1

Related Questions