CGSESC Editorial

PROBLEM LINK:

Practice

Setter - K.S.K Vamsi

Editorial - K.S.K Vamsi

DIFFICULTY :

Medium

PREREQUISITES :

Permutations and Combinations, Basic Programming

PROBLEM :

Sam is trapped in a 2-D Matrix of size N by M. To escape he needs a key which is at position(i,j) in the matrix. He is at Top-leftmost Position and the door is at Bottom -rightmost position. He can only travel right or down. Find the no of ways in which he can escape from the matrix.

EXPLANATION :

The Problem can be broken down into two sub-problems one going from start to key and another starting from key all the way to end. So basically if we solve the problem from start to key we can similarly extend that from key to end. Go through this link to find the no of ways from start to key here. We can similarly
derive a formula from key to end. The final answer is the multiplication of two partial answers.

SOLUTION :

Setter’s solution can be found here