This is from a Kickstart problem:

Note: The Manhattan distance between two squares (r1,c1) and (r2,c2) is defined as |r1 - r2| + |c1 - c2|, where |*| operator denotes the absolute value.

Then in the analysis:

Note that the manhattan distance has an equivalent formula:

dist((x1, y1), (x2, y2)) = max(abs(x1 + y1 - (x2 + y2)), abs(x1 - y1 - (x2 - y2)))

This formula is based on the fact that for any point, the set of points within a manhattan distance of K form a square rotated by 45 degrees. The benefit of this formula is that if we fix (x2, y2), the distance will be maximized when x1 + y1 and x1 - y1 are either maximized or minimized.

Could someone explain in more details how this formula can be derived?

没有正确的解决方案

许可以下: CC-BY-SA归因
不隶属于 cs.stackexchange
scroll top