# Shortest Path – 5

## 18 thoughts on “Shortest Path – 5”

1. Supratim |

Hi Catcracker,

I can’t understand the king’s problem.
Can u elaborate a little. I mean how it is going only upto 3rd row & how the numbers are calculated?

2. Supratim, If the king has exactly 5 moves, and it has to return to the bottom row, it cannot move upwards beyond the third row (i.e. 2 upward steps) as if it takes 3 steps up, it would need 3 more steps to reach back to the bottom, i.e. a minimum of 6 steps.

The way to calculate the numbers I had covered in an earlier post here: https://crackthecat.wordpress.com/2013/02/14/shortest-paths-4-an-alternative-approach/

Basically the logic is that we start from the endpoint and move backwards. The approach is actually based on an algorithm from Operations Research (sometimes known as the stagecoach algorithm I believe, though I am not sure!)

regards
J

3. Ravi |

beautiful :O

4. Sakshi |

Hi,
In kings problem, alternatively we can do like this:
King can move either diagonal or horizontal. So, possible cases are
DDDDH+DDHHH+HHHHH= 5C4+5C2+1= 5+10+1=16.
But, answer is 21. Where am I missing things?

• Sakshi, when you are doing DDDDH the D could be Up Up Down Down or Up Down Up Down, this adds a few cases. See if this solves the confusion?

regards
J

5. Sakshi |

revisited question:
Choosing 4 diagonales: no three or 4 continous diagonal moves are possible.
Choosing 2 diagonales: 2 continous diagonal moves are possible.
still not getting correct ans.

6. 3 or 4 diagonal are possible….consider Up Up Down Down Flat…or U U D F D….

Which is why I prefer my method, it is more reliable than listing each and every case 🙂

regards
J

7. Sir, I have read the previous post shortest path 4, I am able to calculate what number will appear at the points. However, regarding the king’s problem I have not been able to figure out how you have calculated the numbers. Adding right+ below doesnt fit .

• Here you are moving horizontally, so you add all the numbers in the squares that are reachable diagonally or straight to the right….all the places to which you could have moved from the current location.

regards
J

• Savio Poulose |

Sir, thank you so much for the wonderful post on this topic.
I have one query which I tried understanding myself and couldn’t find an explanation.
I just wanted to know why the King can’t move vertically downward? It is an allowable move right for the king? specially in the 2nd last and 3rd last rows.

• Savio, it is an allowable move all right….but if you move vertically at any point then we will need a minimum of 6 moves and we want the job to be done in 5 moves. If you want to get to office in the minimum time, you will not usually set out in the opposite direction (even though it is a 2 way road) right?

regards
J

8. p |

Sir, In first question suppose there is one diagonal (joining 35 and 5 ). thn wat will be the no. of ways??

• 2 * 1 * 5 = 10 ways – since any shortest path will have to pass through that.

regards
J

9. Renu |

Sir, I tried but dint able to get how u arrived to 29 @ Row 1& Column 2 for 1st que? Please elaborate. M not getting how to move thru missing grid line portion. Have gone thru earlier post too of shortest path but somehow couldn’t able to reach the ans. Thanks a lot 🙂

• If movement is to be done from top left to bottom right, you should always move starting from bottom right to top left. If you can’t understand it though, leave it. Too close to the exam to risk playing with a new concept which you aren’t crystal clear about!

regards
J

10. pranay |

Hi ,I have understood example number 4and 5 of yours.I have a similar question but am not able to get the right answer using this method.Can u please help.I am not able to attach the file here.

• Perhaps you could upload it somewhere and post a link? Else I won’t be able to help! Mind-reading, alas, is not among my many talents 🙂

regards
J

11. Thank you sir! Your approach is too good!