Problem 15
Starting in the top left corner of a 2×2 grid, there are 6 routes (without backtracking) to the bottom right corner.

grid
How many routes are there through a 20×20 grid?

Recursion is the first thing which comes into mind in such cases

c++ implementation ::

#include <iostream>
using namespace std;
#define limit 20
long long grid[21][21];
long long walk(int x, int y) {
        if (x > limit || y > limit) return 0;
        if (x == limit && y == limit) return (1);
        if (grid[x][y] != 0) return grid[x][y];
        long long result = 0;
        result += walk(x, y+1);
        result += walk(x+1, y);
        grid[x][y] = result;
        return grid[x][y];
}


int main() {
//      memset(grid, 0, sizeof(grid));
        cout << 2 * walk(1, 0) << endl;
//      system("PAUSE");
        return (0);
}

But if you think from point of view of high school mathematics student, you still can solve it

#include<iostream>
#include <inttypes.h>
using namespace std;

int main()
{
        //additionally,for a generalized solution of gridsize a*b routes=[(a+b)!]/[a!* b!]
        int64_t x=1; //just trying this data type here
        long long int y=1;
        x=37*7*11*31*29*3*4;
        y=115*39;
        cout<<x*y<<endl;

        return 0;
}

This is my last post in this section, this section was just to help get c and c++ fellows started with project euler…try other problems yourself now…gl hf !! 🙂

Advertisements