How many ways across the yard
A forklift crosses a rectangular yard from the top-left bay to the bottom-right one, and may only ever drive right or down. Planning wants the number of distinct routes.
- Movement is only ever one bay right or one bay down.
- Return how many distinct routes reach the far corner.
- A yard with no rows or no columns has no routes.
- A single bay is already the destination: one route.
routesAcross(rows: int, columns: int) → int
C++ needs a compiler and Drill does not host one yet, so this page is the reference rather than an exercise: the problem, worked examples, and the solution in full. To type it out, the same problem runs in Python.
Where you start
int routesAcross(int rows, int columns) {
}Worked examples
| Call | Result |
|---|---|
routesAcross(3, 3) | 6 |
routesAcross(1, 1) | 1 |
routesAcross(2, 3) | 3 |
routesAcross(0, 5) | 0 |
Hint
The routes into a bay are the routes into the bay above plus the routes into the bay to its left. The top row and left column have exactly one each.
Reference solution in C++
int routesAcross(int rows, int columns) {
if (rows <= 0 || columns <= 0) return 0;
std::vector<std::vector<int>> ways(rows, std::vector<int>(columns, 1));
for (int r = 1; r < rows; r++) {
for (int c = 1; c < columns; c++) {
ways[r][c] = ways[r - 1][c] + ways[r][c - 1];
}
}
return ways[rows - 1][columns - 1];
}