scosant
12/17/2012 - 11:16 AM

projecteuler015 - lattice paths

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;
}