I'm not a C programmer, just wanted to make a fast solution to the problem.
Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.
How many such routes are there through a 20×20 grid?
Here's my code:
#include <stdio.h>
#define SIZE 21 // grid size + 1
long long int count_routes(long long int cache[SIZE][SIZE], unsigned short x, unsigned short y) {
if (cache[x][y] != 0) {
return cache[x][y];
}
long long int n = 0;
if (x == 0 && y == 0) {
n = 1;
}
else {
n = 0;
if (x > 0) {
n += count_routes(cache, x-1, y);
}
if (y > 0) {
n += count_routes(cache, x, y-1);
}
}
cache[x][y] = n;
return n;
}
int main(void) {
long long int cache[SIZE][SIZE];
for (int i = 0; i < SIZE; i++) {
for (int j = 0; j < SIZE; j++) {
cache[i][j] = 0;
}
}
printf("%lld\n", count_routes(cache, SIZE-1, SIZE-1));
return 0;
}
Please share your thoughts about what could be improved in it.