17 thoughts on “Shortest Path – 5

  1. 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. 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?

  4. 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.

  5. 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

  6. 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

      • 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

  7. 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

  8. 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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s