Loading...
Loading...
Loading...
Sneha's campus is laid out as a grid of r rows and c columns of blocks. Her hostel is at the top-left block and the library is at the bottom-right block.
From any block she can walk only one block right or one block down. Print the number of different routes from the hostel to the library.
Example 1
Input
2 3
Output
3
The routes are RRD, RDR and DRR, where R is right and D is down.
Example 2
Input
3 3
Output
6
Every route has 2 R moves and 2 D moves in some order, and there are 6 such orders.
Try the problem first. Open one hint at a time.
From the hostel, the first move is either right or down. Every route starts with exactly one of them.
After one step down, what is left is the same problem on a grid with one row fewer. After one step right, one column fewer.
So the count for (r, c) is the count for (r - 1, c) plus the count for (r, c - 1).
When only one row or one column is left, there is exactly one route.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor