projecteuler015 - lattice paths
/* Scott Santarromana
* projecteuler015 - lattice paths
*
* Starting in the top left corner of a 2x2 grid, there are 6 routes
* (without backtrackign) to the bottom right corner. How many routes
* are there through a 20x20 grid?
*/
#include <iostream>
#include <iomanip>
int main(int argc, char* argv[]) {
const unsigned int dim = 5;
int64_t m[dim][dim];
for (unsigned int i = 0; i < dim; i++) {
m[0][i] = 1;
m[i][0] = 1;
}
for (unsigned int j = 1; j < dim; j++) {
for (unsigned int i = 1; i < dim; i++) {
m[i][j] = m[i - 1][j] + m[i][j - 1];
}
}
for (unsigned int j = 0; j < dim; j++) {
for (unsigned int i = 0; i < dim; i++) {
std::cout << std::setfill(' ')
<< std::setw(15) << m[i][j] << "\t";
}
std::cout << std::endl;
}
std::cout << "For a " << dim - 1 << "x" << dim - 1
<< " grid, there are " << m[dim - 1][dim - 1]
<< " paths from the top-left to the top-right.";
return 0;
}