10 thoughts on “Shortest Path – CAT Scan

  1. from B to C:
    Neelam can go from B to corner of D in 6c1 ways and from there to c in 2 ways
    so the answer should have been 90*6c1*2

  2. Hi J! I just read all your blogs regarding shortest path and what I could make out of it is you have broadly divided the approach for these kind of problems in in 2 ways. 1st the direct method of start to finish (when there is no gap/irregular pattern) and the 2nd is reverse approach of finish to start (when there are some kind of gaps/irregularity). Now going by this notion, the CAT-2008 problem should belong to the latter type, which is quite arduous too. But you have applied the 1st approach. I am unable to fathom the similarity between the problem of Shortest Path-5 post and CAT-2008 problem. I am sorry if the answer is too obvious but kindly do help! 😦

    • If the bridge (diagonal road) connecting the corners of the rectangular area P had not been there, then yes, the alternative method would have been the best to apply (though cumbersome). However, that bridge is a game-changer as a path passing through that bridge will be shorter than a path not passing through it (everything else remaining the same). If we assume the length and breadth of each “block” to be 10 then the shortest path not passing through the bridge would be 8 + 6 = 14 but the shortest path via the bridge will be 10 + 2rt2 which is shorter. So we only need to look at paths through that bridge as we are seeking the overall shortest paths.

      regards
      J

      • Thank you. 🙂 Got it. Keeping the bridge start and end point constant the rest of the possibilities is the only thing that is to be found out as the problem concerns only the shortest path. And that completes my full comprehension of your post. Thanks again for such a spontaneous reply and awesome posts!!

      • Assuming for simplicity that the grid consists of squares of side 1 unit. So a possible path could have been 6 units vertically down from A and then 8 units horizontally to the right to reach B.

        regards
        J

  3. HI… I am unable to understand the logic used for computing the possibilities for the B-C path in the Neelam question. Why are we considering the path to C from B as 1 and not 7C2.
    Also if in a similar problem with a 6×12 grid and if the prohibited area lay between the 8 and 9 grid and C was on the 8th vertical line would the solution be the same?
    Please help I have been fretting over the problem for two days now :/

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