Problem

Given two points $P_1$ & $P_2$ in a grid, and you need to reach from one of the cells to the other, Allowed moves will be up, down, left and right. What is the minimum steps required to reach the destination?

Grid Search

TaxiCab Geometry and Manhattan Distance

Going by euclidean geometry in a 2D surface, distance between any given two points $(x_1,y_1)$ and $(x_2,y_2)$ is:

$d = \sqrt{(y_2^{2}-y_1^{2})-(x_2^2-x_1^2)}$

This is the straight line distance drawn as a diagonal between the two points.

The moniker Manhattan distance comes from the grid layout of streets in manhattan, This causes the shortest distance between any two points in a taxicab geometry to be the sum of the absolute values of the differences between both sets of coordinates. The above equation becomes:

$d = |y_2-y_1| + |x_2-x_1|$

This can be visualized as the sum of the length of projection between the two coordinate axes of the diagonal.

References