Given an $N * M$ matrix representing a 2D plane and a start point $(sx, sy)$ and another constant $k$ find all points in the matrix such that it has a Manhattan distance equal to $k$.

This is how I solved it.

Let $(tx, ty)$ be the target point.

$|sx - tx| + |sy - ty| = k$

Since $(sx, sy)$ and $k$ are already known, we can group known terms

$|-tx - ty| = k - |sx - sy|$

$|tx + ty| = k - |sx - sy|$

$|tx + ty| =constant$

All the possible values $ty$ can take are

$ty = constant - tx_i$ where $1 <i < N$

Since the range of $tx$ is $1 < tx < N $ and $ty$ is $1 < ty < M$

I'm not sure if this is correct. Could someone help me out with this one?

  • $\begingroup$ No, it's not correct. The mistake is when you grouped the terms. Absolute value is not parenthesis $\endgroup$ – Andrei May 19 at 5:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.