5
$\begingroup$

This problem is about finding a route on a square grid. The starting point is $(1,1)$ and the target point $(n,m)$. I can move each step from my current point $(x,y)$ either to $(x+y,y)$ or $(x,y+x)$. Now I need to determine if there is a path from $(1,1)$ to $(n,m)$, and if so to return the shortest one.

Now I believe that if I trace back my steps from the input point $(n,m)$ I can always know which move I made out of the two possible ones since if $n=m$ then there is no route, this means I'm always take the smaller coordinate and subtract it from the bigger one. But that means I have at most only one possible route to $(n,m)$ so why was I asked to return the shortest one?

Am I missing anything ?

$\endgroup$
5
$\begingroup$

No, your reasoning seems right. Sometimes problem setters just throw in such things in order to make the problem sound harder than it is.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.