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.

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

How did you get the 8+6?

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

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

As for your other question, I am not sure if I am correctly interpreting your question…in the figure I am getting the prohibited area is anyway not interfering with the shortest path.

Hello,

I am unable to get the solution of Neelam rides. Plz elaborate

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

You are missing the 1 case where she can go to the corner of the big rectangle and not touch D at all…

regard

J

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

How did you get the 8+6?

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

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

B to C is not 1, it is 1 + 2×6 = 13. 7C2 would also include paths through the prohibited region. The logic is explained in question (g) here https://cat100percentile.com/2013/02/13/shortest-path-3/

As for your other question, I am not sure if I am correctly interpreting your question…in the figure I am getting the prohibited area is anyway not interfering with the shortest path.

regards

J